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

Community Detection Algorithms Combining Improved Differential Evolution and Modularity Density

作　　者：冯勇[1] 张冰茹 徐红艳[1] 王嵘冰[1] 张永刚[2] FENG Yong;ZHANG Bingru;XU Hongyan;WANG Rongbing;ZHANG Yonggang(College of Information,Liaoning University,Shenyang 110036,China;Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China)

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

出　　处：《计算机科学与探索》2020年第6期1070-1080,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金,No.71771110;辽宁省社会科学规划基金,No.L18AGL007;吉林大学符号计算与知识工程教育部重点实验室项目,No.93K172018K01;国家留学基金资助项目。

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]