基于多目标进化的复杂网络社区检测  

Complex Network Community Detection Based on Multi-objective Evolution

作　　者：王聪[1] 柴争义[1] WANG Cong;CHAI Zheng-yi(School of Computer Science and Technology,Tianjin University of Technology,Tianjin 300387,China)

机构地区：[1]天津工业大学计算机科学与技术学院,天津300387

出　　处：《计算机技术与发展》2020年第6期44-48,108,共6页Computer Technology and Development

基　　金：国家自然科学基金(U1504613)。

摘　　要：为了准确地发现复杂社区结构,提出一种改进的多目标进化的复杂网络社区检测算法。通过在某一范围内等间距产生多个p参数,再将其代入AP聚类算法通过半监督聚类方式确定聚类个数以及产生初始种群,克服传统的通过随机方式产生的初始解聚类效果不稳定的缺点,且用模拟退火(SA)算法对多目标进化算法进行改进提高种群搜索能力,防止寻优过程陷入局部最优解。分别在不同μ值下仿真40次,以Footbal足球社交网络、Karate-Club网络和Dolphins网络作为测试案例,与传统多目标进化算法以及基于近邻传播(AP)的多目标算法进行实验对比,结果表明文中提出的多目标进化算法在总体上MNI数值更大,即改进效果明显,因此可应用该算法对复杂网络社区进行更加精确的检测。In order to accurately discover the complex community structure,we propose an improved multi-objective evolutionary complex network community detection algorithm.By generating multiple p-parameters at equal intervals in a certain range,and then substituting them into AP clustering algorithm,the number of clusters is determined and the initial population is generated by semi-supervised clustering,so as to overcome the disadvantages of unstable clustering effect of the initial solution of traditional random method.At the same time,the multi-objective evolutionary algorithm is improved by simulated annealing(SA)algorithm to improve the population searching ability and prevent the optimization process from falling into the local optimal solution.Simulating 40 times under differentμvalues respectively,and using Footbal,a football social network,Karate-Club network and Dolphins network as test cases,we compare the proposed algorithm with the traditional multi-objective evolutionary algorithm and the neighbor-based propagation multi-objective evolutionary algorithm.It is concluded that the improved multi-objective evolutionary algorithm has a larger MNI value in the whole,that is,the improvement effect is obvious.Therefore,it can be used to detect the complex network community more accurately.

关 键 词：复杂网络社区 多目标进化 近邻传播(AP)聚类 模拟退火(SA)算法 

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