Computer Science ›› 2014, Vol. 41 ›› Issue (9): 125-131.doi: 10.11896/j.issn.1002-137X.2014.09.024

Previous Articles     Next Articles

Fast Algorithm for Detecting Multi-scale Overlapping Community Structure Based on Information Spreading

LI Hui-jia   

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

Abstract: Most existing community detection methods require the complete graph information,thus is impractical for large-scale technological and social networks.This paper proposed a novel algorithm for the fast detection of multi-scale overlapping community structure.It does not embrace the universal approach but instead tries to focus on local ties and model multi-scale interactions in these networks.It identifies leaders and modules around these leaders using local information.It naturally supports overlapping information by associating each node with a membership vector that describes its involvement of each community.Our method for the first time optimizes the topological entropy of a network and uncovers communities through a novel dynamic system converging to a local minimum by simply updating the membership vector with very low computational complexity.Both theoretical analysis and experiment show that the algorithm can detect communities in social and biological networks fast and accurately.

Key words: Community structure,Complex network,Overlapping,Information spreading,Multi-scale

[1] Barabasi A L,Albert R.Emergence of scaling in random net-works[J].Science,1999,286(5439):509-512
[2] Newman M E J.Fast algorithm for detecting community structure in networks[J].Phys.Rev.E,2004,69:066133
[3] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proc.Natl.Acad.Sci,2002,99(12):7821-7826
[4] Newman M E J,Girvan M.Finding and evaluating communitystructure in networks[J].Phys.Rev.E,2004,69:026113
[5] Li H J,Zhang X S.Analysis of stability of community structure across multiple hierarchical levels[J].Europhys.Lett.,2013,103:58002
[6] Li H J,Wang Y,Wu L Y,et al.Community structure detection based on potts model and spectral characterization[J].Europhys.Lett.,2012,97:48005
[7] Li H J,Wang Y,Wu L Y,et al.Potts model based on a Markov process computation solves the community structure problem effectively[J].Phys.Rev.E,2012,86:016109
[8] Muff S,Rao F,Caflisch A.Local modularity measure for net-work clusterizations[J].Phys.Rev.E,2005,72(5):056107
[9] Gregory S.Finding Overlapping Communities Using DisjointCommunity Detection Algorithms[M]∥Complex Networks.Springer Berlin Heidelberg,2009:47-61
[10] Palla G,Derenyi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435:814-818
[11] 沈华伟,程学旗,陈海强,等.基于信息瓶颈的社区发现[J].计算机学报,2008,31(4):677-686
[12] Raghavan U,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Phys.Rev.E,2007,76(3):036106
[13] Pujol J M,Bejar J,Delgado J.Clustering algorithm for determining community structure in large networks[J].Phys.Rev.E,2006,74(1):016107
[14] 王观玉.基于聚类的复杂网络社团发现算法[J].计算机工程,2011,37(10):58-60
[15] 杨博,刘大有,金弟,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66
[16] Noh J,Rieger H.Random walks on complex networks[J].Phys.Rev.Lett.,2004,92(11):118701
[17] Lai D,Lu H,Nardini C.Enhanced modularity-based community detection by random walk network preprocessing[J].Phys.Rev.E,2010,81(6):066118
[18] Ravasz E,Barabasi A L.Hierarchical organization in complexnetworks[J].Phys.Rev.E,2003,67:026112
[19] Baras J S,Hovareshti P.Efficient and robust communication to-pologies for distributed decision making in networked systems[C]∥Proceedings of 47th IEEE Conference on Decision and Control.2008:2973-2978
[20] Danon L,Duch J,Guilera D,et al.Comparing community structure identification[J].J.Stat.Mech.,2005,29:09008
[21] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].J.Stat.Mech.,2008,10:10008
[22] Rosvall M,Bergstrom C T.Maps of random walks on complex networks reveal community structure[J].Proc.Natl.Acad.Sci.,2008,105(4):1118-1123
[23] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33:452-473
[24] Huh W,et al.Global analysis of protein localization in budding yeast[J].Nature,2003,425:686-691
[25] Jansen R,Gerstein M.Analyzing protein function on a genomic scale:the importance of gold-standard positives and negatives for network prediction[J].Current Opinion in Microbiology,2004,7:535-545
[26] Ruepp A,et al.The FunCat,a functional annotation scheme for systematic classification of proteins from whole genome[J].Nucleic Acids Res,2004,32:5539-5545

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!