Journal of Frontiers of Computer Science and Technology ›› 2020, Vol. 14 ›› Issue (6): 1070-1080.DOI: 10.3778/j.issn.1673-9418.1906040

Previous Articles    

Community Detection Algorithms Combining Improved Differential Evolution and Modularity Density

FENG Yong, ZHANG Bingru, XU Hongyan, WANG Rongbing, ZHANG Yonggang   

  1. 1. College of Information, Liaoning University, Shenyang 110036, China
    2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
  • Online:2020-06-01 Published:2020-06-04

结合改进差分进化和模块密度的社区发现算法

冯勇张冰茹徐红艳王嵘冰张永刚   

  1. 1. 辽宁大学 信息学院,沈阳 110036
    2. 吉林大学 符号计算与知识工程教育部重点实验室,长春 130012

Abstract:

Community detection is the foundation and core of research in the fields of personalized recommendation, group feature collection and social network analysis. However, existing community detection algorithms generally have some problems for dealing with increasingly complex social networks, such as low accuracy, slow convergence rate and limited modularity resolution. The idea of differential evolution and modularity density is introduced into community detection, and a community detection algorithm combining improved differential evolution and modularity density is proposed. Firstly, the algorithm adjusts the mutation strategy and parameters of differential evolution, and then takes the modularity density as the fitness function to overcome the limitation of the modularity resolution, and then corrects the operation according to the community structure to improve the individual quality in the population and accelerate the global convergence. Finally, the proposed method is compared with other popular community detection algorithms on computer generated networks and 5 representative real world networks. The experimental results show that the proposed algorithm has higher accuracy and better convergence performance.

Key words: community detection, social network, differential evolution, modularity density, mutation strategy

摘要:

社区发现是个性化推荐、群体特征归集、社会网络分析等领域研究的基础与核心,而现有社区发现算法在处理日益复杂的社会网络时,存在准确性不高、收敛速度慢、模块度分辨率受限等问题。为此,将差分进化和模块密度思想引入社区发现中,提出了一种结合改进差分进化和模块密度的社区发现算法。该算法首先调整差分进化的变异策略和参数,再将模块密度作为适应度函数以克服模块度分辨率限制;然后根据社区结构进行修正操作,以提高种群中的个体质量,加快全局收敛速度。在计算机生成网络数据集及5个具有代表性的真实世界网络数据集上,与多个应用较为广泛的社区发现算法进行对比实验。实验结果表明所提算法具有更高的准确性和更优的收敛性能。

关键词: 社区发现, 社会网络, 差分进化, 模块密度, 变异策略