吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (5): 1592-1600.doi: 10.13229/j.cnki.jdxbgxb201505031

Previous Articles     Next Articles

Heuristic genetic algorithm associated with spectral analysis uncovering multi-scale community of complex networks

GUO Yu-quan1, LI Xiong-fei1, LIU Xin2   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012,China;
    2.Network Center, Jilin University, Changchun 130022,China
  • Received:2014-05-04 Online:2015-09-01 Published:2015-09-01

RICH HTML

0   

PDF (PC)

290

Abstract: The community structure of complex networks has attracted much attention. However, previous methods can not investigate the multi-scale property of the community. To address this problem, by analyzing conduct function C and average agglomerate probability, a local heuristic heteromorphosis strategy is proposed; then, spectral analysis of complex networks is combined with genetic algorithm; finally a multi-scale community detection algorithm HGASA (Heuristic genetic algorithm with spectral analysis) is proposed. Extensive tests on artificial networks and real world networks justify the superiority of the HGASA algorithm.

Key words: computer application, multiple-scale community, genetic algorithm, heuristic function, local heuristic mutation algorithm

CLC Number: 

  • TP391
[1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
[2] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133.
[3] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E, 2009, 80(2): 026129.
[4] Liu D Y, Jin D, Baquero C, et al. Genetic algorithm with a local search strategy for discovering communities in complex networks[J]. International Journal of Computational Intelligence Systems, 2013, 6(2): 354-369.
[5] Newman M E J. Detecting community structure in networks[J]. European Physical Journal B, 2004, 38(2): 321-330.
[6] Shen H W, Cheng X Q, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A:Statistical Mechanics and Its Applications, 2009, 388(8): 1706-1712.
[7] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[8] Jin D, Yang B, Baquero C, et al. A Markov random walk under constraint for discovering overlapping communities in complex networks[J]. Journal of Statistical Mechanics-Theory and Experiment, 2011(5):P05031.
[9] Alex Arenas, Albert Diaz-Guilera, Conrad J. Synchronization reveals topological scales in complex networks[J]. Physical Review Letters, 2006, 96(11): 114102.
[10] Delvenne J C, Yaliraki S N, Barahona M. Stability of graph communities across time scales[J]. Proceedings of the National Academy of Sciences, 2010, 107(29): 12755-12760.
[11] Cheng X Q, Shen H W. Uncovering the community structure associated with the diffusion dynamics on networks[J]. Journal of Statistical Mechanics-Theory and Experiment, 2010(4):P04024,
[12] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.
[13] Arenas A, Fernandez A, Gomez S. Analysis of the structure of complex networks at different resolution levels[J]. New Journal of Physics, 2008, 10(5): 053039.
[14] Shen H W, Cheng X Q. Spectral methods for the detection of network community structure: a comparative analysis[J]. Journal of Statistical Mechanics-Theory and Experiment, 2010(10):P10020,
[15] Shen H W, Cheng X Q, Wang Y Z, et al. A dimensionality reduction framework for detection of multiscale structure in heterogeneous networks[J]. Journal of Computer Science and Technology, 2012, 27(2): 341-357.
[16] Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms[EB/OL].[2013-07-08] .http://arxiv.org/abs/0711.0491.
[17] Gregory S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010, 12(10):103018
[18] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4):046110.
[19] Lee C, Reid F, Mcdaid A, et al. Detecting highly overlapping community structure by greedy clique expansion[EB/OL].[2013-09-22].http://arxiv.org/abs/1002.1827.
[20] Zachary W. An information flow modelfor conflict and fission in small groups1[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[21] Lusseau D. The emergent properties of a dolphin social network[J]. Proceedings of the Royal Society of London Series B: Biological Sciences, 2003, 270(Suppl 2): 186-188.
[1] WU Wei-nan,CUI Nai-gang,GUO Ji-feng,ZHAO Yang-yang. Distributed integrated method for mission planning of heterogeneous unmanned aerial vehicles [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1827-1837.
[2] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[3] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[4] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[5] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[6] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[7] JIAO Yu-ling, ZHANG Peng, TIAN Guang-dong, XING Xiao-cui, ZOU Lian-hui. Slotting optimization of automated warehouse based on multi-population GA [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1398-1404.
[8] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[9] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[10] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[11] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[12] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[13] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[14] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[15] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd