Computer Science ›› 2016, Vol. 43 ›› Issue (Z6): 395-399.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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!