分解多目标优化揭示复杂网络社区层次结构

doi:10.3969/j.issn.1001-2400.2013.03.031

J4 ›› 2013, Vol. 40 ›› Issue (3): 205-211.doi: 10.3969/j.issn.1001-2400.2013.03.031

分解多目标优化揭示复杂网络社区层次结构

陈国强^1,2;王宇平¹

(1. 西安电子科技大学计算机学院，陕西西安 710071；
2. 河南大学计算机与信息工程学院，河南开封 475004)

收稿日期:2012-02-17 出版日期:2013-06-20 发布日期:2013-07-29
通讯作者: 陈国强
作者简介:陈国强(1977-)，男，西安电子科技大学博士研究生，E-mail: chengq08@163.com．
基金资助:
国家自然科学基金资助项目(61272119,61203372)

Revealing of the hierarchy community of the complex network by decomposition multi-objective optimization

CHEN Guoqiang^1,2;WANG Yuping¹

(1. School of Computer Science and Technology, Xidian Univ., Xi'an 710071， China;
2. School of Computer and Information Engineering, Henan Univ., Kaifeng 475004， China)

Received:2012-02-17 Online:2013-06-20 Published:2013-07-29
Contact: CHEN Guoqiang

摘要/Abstract

摘要：

提出了一种求解复杂网络社区检测的新算法．新算法将社区检测问题构造成多目标优化问题，通过在多个目标之间权衡折中，实现在更广泛的空间进行社区结构检测，克服了传统单目标优化存在解单一的缺陷．算法采用MOEA/D框架，运用Tchebycheff分解技术，引入基于加权法的模拟退火局部搜索算子，扩大了搜索范围，使算法不易陷入局部最优解．最后，在计算机生成的网络数据集以及真实网络数据集上对算法进行了仿真实验．结果表明，该算法与已有算法相比，具有较高的检测正确率，计算量较小．同时，获得的多个Pareto最优解有助于揭示复杂网络社区的层次结构．

关键词: 复杂网络, 社区检测, 多目标优化, 层次结构

Abstract:

A new algorithm for community detection of complex networks is proposed. The problem of community detection is considered as multi-objective optimization problem. Tradeoff among multi-objectives realizes the detection of the community structure in a wider spread space, the disadvantages of the traditional single optimization algorithm is overcome. The MOEA/D framework is adopted and the Tchebycheff decomposition technique is used. A simulated annealing based weighted-sum method is used to perform local search which can expand the search scope, and not easily fall into local optimal solution. Finally, simulation experiments are done to test the algorithm using artificial and reality networks. The results show that, compared with existing algorithms, the algorithm has a higher detection accuracy and a small amount of computation, and can reveal the hierarchy community structure of the complex network by Pareto optimal solutions.

Key words: complex networks, community detection, multi objective optimization, hierarchy structure

中图分类号:

TP393

陈国强;王宇平. 分解多目标优化揭示复杂网络社区层次结构[J]. J4, 2013, 40(3): 205-211.

CHEN Guoqiang;WANG Yuping. Revealing of the hierarchy community of the complex network by decomposition multi-objective optimization[J]. J4, 2013, 40(3): 205-211.

参考文献

［1］ Papadopoulos S, Kompatsiaris Y, Vakali A, et al. Community Detection in Social Media Performance and Application Considerations［J］. Data Mining and Knowledge Discovery, 2012, 24(3): 515-554.
［2］ Girvan M, Newman M E J. Community Structure in Social and Biological Networks［J］. Proc Natl Acad Sci, 2002, 99(12): 7821-7826.
［3］ Wu Jianshe, Jiao Licheng, Jin Chao, et al. Overlapping Community Detection Via Network Dynamics［J］. Physical Review E, 2012, 85(1): 016115-1-016115-7.
［4］付立冬, 高琳. 特征向量的核方法检测网络社团结构［J］. 西安电子科技大学学报, 2012, 39(2): 207-214.
Fu Lidong, Gao Lin. Kernel K-means Clustering Algorithm for Detecting Communities in Complex Networks Based on Eigenvector［J］. Journal of Xidian University, 2012, 39(2): 207-214.
［5］ Psorakis I, Roberts S, Ebden M. Overlapping Community Detection Using Bayesian Non-negative Matrix Factorization［J］. Physical Review E, 2011, 83(6): 066114-1-066114-9.
［6］ Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks［J］. Phys Rev E, 2004, 69(2): 026113-1-026113-15.
［7］ Fortunato S, Barthélemy M. Resolution Limit in Community Detection［J］. Proc Natl Acad Sci, 2007,104(1): 36-41.
［8］ Li Z P, Zhang S H, Wang R S, et al. Quantitative Function for Community Detection［J］. Phys Rev E, 2008, 77(3): 036106-1-036106-9.
［9］ Chen Guoqiang, Wang Yuping. Community Detection in Complex Networks Using Immune Clone Selection Algorithm［J］. International Journal of Digital Content Technology and Its Applications, 2011, 5(6): 182-189.
［10］ Maoguo Gong, Bao Fu, Licheng Jiao, et al. Memetic Algorithm for Community Detection in Networks［J］. Physical Review E, 2011, 84(4): 056101-1-056101-9.
［11］陈国强, 王宇平. 基于极值优化模块密度的复杂网络社区检测［J］. 华中科技大学学报(自然科学版), 2011, 39(4): 82-85.
Chen Guoqiang, Wang Yuping. Community Detection in Complex Networks Using Extremal Optimization Modularity Density［J］. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2011, 39(4): 82-85.
［12］ Shi Chuan, Zhong Cha, Yan Zhenyu, et al. A Multi-objective Approach for Community Detection in Complex Network［C］//2010 IEEE Congress on Evolutionary Computation. Barcelona: IEEE, 2010: 18-23.
［13］ Pizzuti C. A Multi-objective Genetic Algorithm for Community Detection in Networks［C］//2009 21st IEEE International Conference on Tools with Artificial Intelligence. New Jersey: IEEE, 2009: 379-386.
［14］ Martin R, Carl T B. An Information-theoretic Framework for Resolving Community Structure in Complex Networks［J］. Proc Natl Acad Sci, 2007, 104(18): 7327-7331.
［15］ Zhang Qingfu, Li Hui. Moea/D: a Multiobjective Evolutionary Algorithm Based on Decomposition［J］. IEEE Trans on Evolutionary Computation, 2007, 11(6): 712-731.
［16］ Lancichinetti A, Fortunato S, Radicchi F. Benchmark Graphs for Testing Community Detection Algorithms［J］. Physical Review E, 2008, 78(4): 046110-1-046110-5.
［17］ Danon L, Díaz-Guilera A, Duch J, et al. Comparing Community Structure Identification［J］. Journal of Statistical Mechanics, 2005, 2005(9): 09008-1-09008-7.
［18］ Zachary W W. An Information Flow Model for Conflict and Fission in Small Groups［J］. Journal of Anthropological Research, 1977, 33(4): 452-473.
［19］ Lusseau D. The Emergent Properties of Dolphin Social Network［J］. Biology Letters, Proc R Soc, 2003, 270(S2): S186-S188.
［20］ Newman N E J. Modularity and Community Structure in Networks［J］. Proc Natl Acad Sci, 2006,103(3): 8577-8582.

[1]	张宇鹏,吴自力,陈鸣,张璐璐. 面向交叉微服务链的任务调度优化[J]. 西安电子科技大学学报, 2021, 48(6): 32-39.
[2]	杜文占,余志勇,杨剑,姜海滨. 改进NSGA-II算法及监测天线部署优化研究[J]. 西安电子科技大学学报, 2021, 48(5): 239-248.
[3]	杨五四,陈莉,王毅,张茂省. 一种适应度排序的高维多目标粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(3): 78-84.
[4]	刘天宇,王翥. 一种多样性控制的多目标粒子群算法[J]. 西安电子科技大学学报, 2021, 48(3): 106-114.
[5]	张书博,任淑霞,吴涛. 结合概率矩阵的改进谱聚类社区发现算法[J]. 西安电子科技大学学报, 2019, 46(3): 167-172.
[6]	王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019, 46(1): 130-136.
[7]	韩亚敏;柴争义;李亚伦;朱思峰. 长尾群组推荐的免疫多目标优化实现[J]. 西安电子科技大学学报, 2018, 45(3): 109-116.
[8]	王丹青;李萍. 利用GEK代理模型的天线快速多目标优化设计[J]. 西安电子科技大学学报, 2018, 45(2): 129-134+165.
[9]	王明昭;王宇平;王晓丽;卫珍. 一种均匀聚集距离的改进NSGA-Ⅱ算法[J]. 西安电子科技大学学报, 2016, 43(3): 49-54+130.
[10]	雷雨;焦李成;公茂果;李玲玲. 求解多目标考试时间表问题的NNIA改进算法[J]. 西安电子科技大学学报, 2016, 43(2): 157-161+192.
[11]	代才;王宇平;何晓光. 高维多目标问题的排序新方法[J]. J4, 2014, 41(6): 89-94.
[12]	董宁;王宇平. 求解约束优化问题的偏好多目标进化算法[J]. J4, 2014, 41(1): 98-104+188.
[13]	王玙;高琳. 动态网络桥系数增量聚类算法[J]. J4, 2013, 40(1): 30-35.
[14]	刘若辰;焦李成;雷七峰;方玲芬. 一种新的差分进化约束优化算法[J]. J4, 2011, 38(1): 47-53.
[15]	付立东;高琳. 模块密度谱分的网络社团发现方法[J]. J4, 2010, 37(5): 916-920+965.

分解多目标优化揭示复杂网络社区层次结构

Revealing of the hierarchy community of the complex network by decomposition multi-objective optimization

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0