A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks

作者：Li, Yadong; Liu, Jing^*; Liu, Chenlong

来源：Soft Computing, 2014, 18(2): 329-348.

DOI：10.1007/s00500-013-1060-4

• Signed social networks
• Memetic algorithms
• Evolutionary algorithms
• Community detection problems

To detect communities in signed networks consisting of both positive and negative links, two new evolutionary algorithms (EAs) and two new memetic algorithms (MAs) are proposed and compared. Furthermore, two measures, namely the improved modularity Q and the improved modularity density D-value, are used as the objective functions. The improved measures not only preserve all properties of the original ones, but also have the ability of dealing with negative links. Moreover, D-value can also control the partition to different resolutions. To fully investigate the performance of these four algorithms and the two objective functions, benchmark social networks and various large-scale randomly generated signed networks are used in the experiments. The experimental results not only show the capability and high efficiency of the four algorithms in successfully detecting communities from signed networks, but also indicate that the two MAs outperform the two EAs in terms of the solution quality and the computational cost. Moreover, by tuning the parameter in D-value, the four algorithms have the multi-resolution ability.

• 出版日期2014-2
• 单位西安电子科技大学