2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7): 873-882. doi: 10.3724/SP.J.1004.2011.00873
引用本文: 金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7): 873-882. doi: 10.3724/SP.J.1004.2011.00873
JIN Di, LIU Jie, YANG Bo, HE Dong-Xiao, LIU Da-You. Genetic Algorithm with Local Search for Community Detection in Large-scale Complex Networks. ACTA AUTOMATICA SINICA, 2011, 37(7): 873-882. doi: 10.3724/SP.J.1004.2011.00873
Citation: JIN Di, LIU Jie, YANG Bo, HE Dong-Xiao, LIU Da-You. Genetic Algorithm with Local Search for Community Detection in Large-scale Complex Networks. ACTA AUTOMATICA SINICA, 2011, 37(7): 873-882. doi: 10.3724/SP.J.1004.2011.00873

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

doi: 10.3724/SP.J.1004.2011.00873

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

  • 摘要: 基于遗传算法的复杂网络社区探测是当前的研究热点. 针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上, 给出一种快速、有效的局部搜索变异策略, 同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的, 采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Genetic algorithm with local search, LGA). 在基准网络及大规模复杂网络上对LGA进行测试, 并与当前具有代表性的社区探测算法进行比较, 实验结果表明了文中算法的有效性与高效性.
  • [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
  • 加载中
计量
  • 文章访问数:  2910
  • HTML全文浏览量:  89
  • PDF下载量:  1577
  • 被引次数: 0
出版历程
  • 收稿日期:  2010-07-19
  • 修回日期:  2011-01-12
  • 刊出日期:  2011-07-20

目录

    /

    返回文章
    返回