基于双编码的重叠社团检测多目标优化方法

A Dual Representation-Based Multi-Objective Evolutionary Algorithm for Overlapping Community Detection

近年来,多目标进化方法已被广泛应用于重叠社团检测问题并取得了较好的社团划分性能.如何设计合适的个体编码以及进化策略是提高基于多目标进化重叠社团检测算法性能的重要因素.为此,本文设计了一种双编码表示方法对非重叠社团结构和重叠点分别进行编码,能够有效解码得到重叠社团结构.在双编码表示的基础上,本文提出了一种基于双编码的重叠社团检测多目标优化方法(DRMOEA).在DRMOEA中,为了获得好的初始个体并提高算法检测性能,本文提出了一种基于社团边界点的初始化策略.除此之外,针对双编码中的重叠点编码部分,本文提出了基于精英个体边界点的交叉策略,该策略利用社团边界信息引导种群向好的方向进化,从而有效提高了算法的检测性能.最后,在9个真实世界网络上的实验结果表明DRMOEA算法优于其他5个代表性重叠社团检测算法.

In recent years,the multi-objective evolutionary methods have been widely used for solving overlapping community detection problem and have achieved good community division performance.To design appropriate individual encoding and evolution strategies is important to improve the performance of multi-objective overlapping community detec⁃tion evolutionary algorithm.To this end,a dual representation method is designed to encode the non-overlapping communi⁃ty structures and overlapping nodes respectively,which can effectively obtain the overlapping community structures.On the basis of the dual representation,this paper proposes a dual representation-based multi-objective evolutionary algorithm for overlapping community detection(DRMOEA).In DRMOEA,an initialization strategy based on community boundary nodes is suggested to obtain good initial individuals,with the aim to improve the detection performance of the algorithm.In addition,for the overlapping part of the dual-representation,this paper proposes a crossover strategy according to the bound⁃ary nodes of elite individuals,which uses community boundary information to guide the evolution of the population towards a better direction.Finally,the experimental results on nine real-world networks show that the proposed DRMOEA is better than five representative baseline overlapping community detection algorithms.