基于多目标优化的网络社区发现方法  

Discovering Network Community Based on Multi-Objective Optimization

作　　者：黄发良[1] 张师超[2] 朱晓峰[2,3] 

机构地区：[1]福建师范大学软件学院,福建福州350007 [2]广西师范大学计算机科学与信息工程学院,广西桂林541000 [3]School of Information Technology and Electrical Engineering,University of Southern Queensland,Australia

出　　处：《软件学报》2013年第9期2062-2077,共16页Journal of Software

基　　金：国家自然科学基金(61170131,61263035);澳大利亚ARC(DP0985456);国家高技术研究发展计划(863)(2012AA011005);国家重点基础研究发展计划(973)(2013CB329404);教育部人文社会科学研究青年基金(12YJCZH074);福建师范大学优秀青年骨干教师培养基金(fjsdjk2012082);科学计算与智能信息处理广西高校重点实验室开放基金(GXSCIIP201212)

摘　　要：社区发现是复杂网络挖掘中的重要任务之一,在恐怖组织识别、蛋白质功能预测、舆情分析等方面具有重要的理论和应用价值.但是,现有的社区质量评判指标具有数据依赖性与耦合关联性,而且基于单一评判指标优化的网络社区发现算法有很大的局限性.针对这些问题,将网络社区发现问题形式化为多目标优化问题,提出了一种基于多目标粒子群优化的网络社区发现算法MOCD-PSO,它选取模块度Q、最小最大割MinMaxCut与轮廓(silhouette)这3个指标进行综合寻优.实验结果表明,MOCD-PSO算法具有较好的收敛性,能够发现分布均匀且分散度较高的Pareto最优网络社区结构集,并且无论与单目标优化方法(GN与GA-Net)相比较,还是与多目标优化算法(MOGANet与SCAH-MOHSA)相比较,MOCD-PSO算法都能在无先验信息的条件下挖掘出更高质量的网络社区.Community discovery is an important task in mining complex networks, and has important theoretical and application value in the terrorist organization identification, protein function prediction, public opinion analysis, etc. However, existing metrics used to measure quality of network communities are data dependent and have coupling relations, and the community discovery algorithms based on optimizing just one metric have a lot of limitations. To address the issues, the task to discover network communities is formalized as a multi-objective optimization problem. An algorithm, MOCD-PSO, is used to discover network communities based on multi-objective particle swarm optimization, which constructs objective function with modularity Q, MinMaxCut and silhouette. The experimental results show that the proposed algorithm has good convergence and can find Pareto optimal network communities with relatively well uniformand dispersive distribution. In addition, compared with the classical algorithms based on single objective optimization （GN, GA-Net） and multi-objective optimization （MOGA-Net,SCAH-MOHSA）, the proposed algorithm requires no input parameters and can discover the higher-quality community structure in networks.

关 键 词：复杂网络 社区挖掘 多目标粒子群优化 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]