局部搜索与遗传算法结合的大规模复杂网络社区探测

金弟; 刘杰; 杨博; 何东晓; 刘大有

doi:10.3724/SP.J.1004.2011.00873

局部搜索与遗传算法结合的大规模复杂网络社区探测

doi: 10.3724/SP.J.1004.2011.00873

金弟^1,2,
刘杰^1,2,
杨博^1,2,
何东晓^1,2,
刘大有^1,2

1.
吉林大学计算机科学与技术学院长春 130012;
2.
吉林大学符号计算与知识工程教育部重点实验室长春 130012

计量
- 文章访问数: 2966
- HTML全文浏览量: 92
- PDF下载量: 1584
- 被引次数: 0
出版历程
- 收稿日期: 2010-07-19
- 修回日期: 2011-01-12
- 刊出日期: 2011-07-20

Genetic Algorithm with Local Search for Community Detection in Large-scale Complex Networks

JIN Di^1,2,
LIU Jie^1,2,
YANG Bo^1,2,
HE Dong-Xiao^1,2,
LIU Da-You^1,2

1.
College of Computer Science and Technology, Jilin University, Changchun 130012;
2.
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012

摘要

摘要: 基于遗传算法的复杂网络社区探测是当前的研究热点. 针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上, 给出一种快速、有效的局部搜索变异策略, 同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的, 采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Genetic algorithm with local search, LGA). 在基准网络及大规模复杂网络上对LGA进行测试, 并与当前具有代表性的社区探测算法进行比较, 实验结果表明了文中算法的有效性与高效性.
- 复杂网络 /
- 社区探测 /
- 网络聚类 /
- 遗传算法 /
- 局部搜索
Abstract: Detecting communities from complex networks by genetic algorithm has triggered a great common interest. For this problem, a genetic algorithm with local search (LGA) which employs network modularity Q as objective function is given in this work. An effective as well as efficient mutation method combined with a local search strategy is proposed based on our profound analysis on local monotonicity of function Q, meanwhile, a label propagation based method is adopted to produce the accurate and diverse initial population, which can further improve the search efficiency of LGA. The proposed LGA has been tested on both benchmark networks and some large-scale complex networks, and compared with some competitive community detection algorithms. Experimental result has shown that LGA is highly effective and efficient for discovering community structure.
- Complex network /
- community detection /
- network clustering /
- genetic algorithm /
- local search

HTML全文

参考文献(1)

[1]

Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks. Nature, 1998, 393(6638): 440-442[2] Adamic L A, Huberman B A, Barabasi A L, Albert R, Jeong H, Bianconi G. Power-law distribution of the world wide web. Science, 2000, 287(5461): 2115a[3] Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826[4] Yan G, Chen G, Lv J, Fu Z Q. Synchronization performance of complex oscillator networks. Physical Review E, 2009, 80(5): 056116[5] Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3-5): 75-174[6] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113[7] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 066133[8] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks. Nature, 2005, 433(7028): 895-900[9] Newman M E J. Modularity and community structure in networks. Proceedings of National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582[10] Lv Z, Huang W. Iterated tabu search for identifying community structure in complex networks. Physical Review E, 2009, 80(2): 026130[11] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints. Physical Review E, 2009, 80(2): 026129[12] Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A, 2010, 389(7): 1493-1500 [13] Brandes U, Delling D, Gaertler M, Goerke R, Hoefer M, Nikoloski Z, Wagner D. Maximizing modularity is hard. arXiv: physics/0608255, 2006[14] Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms. arXiv: 0711.0491, 2007[15] He Dong-Xiao, Zhou Xu, Wang Zuo, Zhou Chun-Guang, Wang Zhe, Jin Di. Community mining in complex networks-clustering combination based genetic algorithm. Acta Automatica Sinica, 2010, 36(8): 1160-1170(何东晓, 周栩, 王佐, 周春光, 王喆, 金弟. 复杂网络社区挖掘---基于聚类融合的遗传算法. 自动化学报, 2010, 36(8): 1160-1170)[16] He Dong-Xiao. Research on Intelligent Algorithms for Network Community Mining [Master dissertation], Jilin University, China, 2010(何东晓. 网络社区智能挖掘算法的研究 [硕士学位论文], 吉林大学, 中国, 2010)[17] Li S, Chen Y, Du H, Feldman M W. A genetic algorithm with local search strategy for improved detection of community structure. Complexity, 2010, 15(4): 53-60[18] Pizzuti C. Community detection in social networks with genetic algorithms. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM, 2008. 1137-1138[19] Pizzuti C. A multi-objective genetic algorithm for community detection in networks. In: Proceedings of the 21st IEEE International Conference on Tools with Artificial Intelligence. New Jersey, USA: IEEE, 2009. 379-386[20] Shi C, Yan Z, Wang Y, Cai Y, Wu B. A genetic algorithm for detecting communities in large-scale complex networks. Advances in Complex Systems, 2010, 13(1): 3-17 [21] Jin D, He D, Liu D, Baquero C. Genetic algorithm with local search for community mining in complex networks. In: Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence. Arras, France: IEEE, 2010. 105-112[22] Mezura-Montes E, Coello C A C. A simple multimembered evolution strategy to solve constrained optimization problems. IEEE Transactions on Evolutionary Computation, 2005, 9(1): 1-17 [23] Fortunato S, Barthelemy M. Resolution limit in community detection. Proceedings of National Academy of Sciences of the United States of America, 2007, 104(1): 36-41 [24] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007, 76(3): 036106[25] Danon L, Diaz-Guilera A, Duch J, Arenas A. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9): P09008-09008[26] Leskovec J, Lang K J, Dasgupta A, Mahoney M W. Statistical properties of community structure in large social and information networks. In: Proceedings of the 17th International Conference on World Wide Web. Beijing, China: ACM, 2008. 695-704[27] Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4): 452-473[28] Lusseau D. The emergent properties of a dolphin social network. Proceedings of the Royal Society B: Biological Sciences, 2003, 270(S2): 186-188[29] Gleiser P M, Danon L. Community structure in jazz. Advances in Complex Systems, 2003, 6(4): 565-573[30] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structures of complex networks in nature and society. Nature, 2005, 435(7043): 814-818[31] Newman M E J. The structure of scientific collaboration networks. Proceedings of National Academy of Sciences of the United States of America, 2001, 98(2): 404-409

施引文献

资源附件(0)

访问统计