Computer Science ›› 2016, Vol. 43 ›› Issue (Z6): 395-399, 412.doi: 10.11896/j.issn.1002-137X.2016.6A.094

Previous Articles     Next Articles

Near Linear Time Community Detection Algorithm Based on Dynamical Evolution

REN Luo-kun, LI Hui-jia and JIA Chuan-liang   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Detecting communities is is crucial for analyzing and designing complicated natural and engineering network.The existing community detection algorithms rely heavily on optimization and heuristic methods,which can not balance computational efficiency and accuracy simultaneously.Thus we proposed an evolutionary algorithm which uses a new dynamical system based on community membership vector to formulate the conditions driving the convergence of dynamics trajectory.Then,we proposed a quality function,which can unify the conventional algorithms by selecting appropriate parameters.Furthermore,considering the difficulty in choosing parameters,we established a graph generative model according to the network prior information,by which the optimum formalism of the quality function can be obtained automatically.Our algorithm is highly efficient and the computational complexity is nearly linear with the number of all nodes in a sparse network.Finally,extensive experiments were performed in both artificial and real networks,which reveal much useful information.

Key words: Community detection,Evolutionary computation,Dynamical iterative systems,Near linear time

[1] Wang X F,Chen G.Complex networks:Small-world,scale-free and beyond[J].IEEE Circuits and System Magazine,2003,3(1):6-20
[2] Newman M E J.Networks:an introduction[M].Oxford University Press,2010
[3] Lones M A,Caves A P,Stepney S,et al.Artificial biochemical networks:Evolving dynamical systems to control systems[J].IEEE Transactions on Evolutionary Computation,2012,18(2):145-166
[4] Palafox L,Noman N,Iba H.Reverse engineering of gene regulatory networks using dissipative particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2013,7(4):77-587
[5] Li H J,Daniels J.Social significance of community structure:Statistical view[J].Physical Review E,2015,91(1):012801
[6] Fortunato S.Community detection in graphs[J].Physics Reports,2010,6(3-5):75-174
[7] 李慧嘉.基于信息扩散的多尺度重叠社团快速探测算法[J].计算机科学,2014,1(9):125-131
[8] Pizzuti C.A multi-objective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutio-nary Computation,2012,16(3):418-430
[9] Liu Y,Moer J,Aviyente S.Network Community Structure Detection for Directional Neural Networks Inferred From Multichannel Multisubjective EEG Data[J].IEEE Transactions on Biomedical Engineering,2014,61(7):1919-1930
[10] 李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,8(2):301-312

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .