| 摘要: |
| 社区发现是复杂网络挖掘中的重要任务之一,在恐怖组织识别、蛋白质功能预测、舆情分析等方面具有重要的理论和应用价值.但是,现有的社区质量评判指标具有数据依赖性与耦合关联性,而且基于单一评判指标优化的网络社区发现算法有很大的局限性.针对这些问题,将网络社区发现问题形式化为多目标优化问题,提出了一种基于多目标粒子群优化的网络社区发现算法MOCD-PSO,它选取模块度Q、最小最大割MinMaxCut 与轮廓(silhouette)这3 个指标进行综合寻优.实验结果表明,MOCD-PSO 算法具有较好的收敛性,能够发现分布均匀且分散度较高的Pareto 最优网络社区结构集,并且无论与单目标优化方法(GN 与GA-Net)相比较,还是与多目标优化算法(MOGANet与SCAH-MOHSA)相比较,MOCD-PSO 算法都能在无先验信息的条件下挖掘出更高质量的网络社区. |
| 关键词: 复杂网络 社区挖掘 多目标粒子群优化 |
| DOI：10.3724/SP.J.1001.2013.04400 |
| 分类号: |
| 基金项目:国家自然科学基金(61170131, 61263035);澳大利亚ARC(DP0985456);国家高技术研究发展计划(863)(2012AA011005);国家重点基础研究发展计划(973)(2013CB329404);教育部人文社会科学研究青年基金(12YJCZH074);福建师范大学优秀青年骨干教师培养基金(fjsdjk2012082);科学计算与智能信息处理广西高校重点实验室开放基金(GXSCIIP201212) |
|
| Discovering Network Community Based on Multi-Objective Optimization |
|
HUANG Fa-Liang1, ZHANG Shi-Chao2, ZHU Xiao-Feng2,3
|
|
1.Faculty of Software, Fujian Normal University, Fuzhou 350007, China;2.College of Computer Science and Information Technology, Guangxi Normal University, Guilin 541000, China;3.School of Information Technology and Electrical Engineering, University of Southern Queensland, Australia
|
| Abstract: |
| 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 uniform and 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. |
| Key words: complex network communities mining multi-objective particle swarm optimization |
