一种基于差分进化的社团检测算法

A Community Detection Algorithm Using Differential Evolution

复杂网络的社团结构分析可抽象为一个优化问题,用进化算法求解。进化类算法的一个基本问题是如何把问题的候选解编码到进化个体中。本文将索引局部邻接表示法用于社团检测进化算法的个体表示,把社团结构分析转化为一个整数优化问题。在该个体表示方法的基础上,提出了一种基于差分进化的社团检测算法。在一组合成网络和真实网络上验证了算法性能,并与两种基于遗传算法的典型社团检测进化算法进行了对比。实验结果表明,当网络社团结构较为清晰时,基于差分进化的算法检测到的社团结构具有更好的质量。

Community structure analysis of complex networks can be modeled as an optimizing problem,and then be solved by Evolution Algorithm（EA）.One fundamental issue of EA is how to encode a candidate solution into an evolution individual.In this paper,the Indexed Locus-based Adjacency Representation（ILAR） of evolution individual encoding for the community detection problem is proposed.Therefore,a community detection problem can be converted to a discrete integer optimization problem.Based on the ILAR,a community detection algorithm that uses Differential Evolution（DE） as the search engine is developed.A number of experiments are conducted on synthesized and real-world networks to verify the performance of the proposed algorithm,and the results are compared against those of two typical community detection algorithms based on Genetic Algorithm（GA）.The experiment results show that the community structure discovered by the proposed DE-based algorithm generally has better quality than those of the two compared algorithms as the community structure of the analyzed network is sound.