Computer Science ›› 2014, Vol. 41 ›› Issue (Z6): 258-261.

Previous Articles     Next Articles

Fast Algorithm for Overlapping Community Detection in Directed Networks

LI Li-jie,CHEN Duan-bing and WANG Guan-nan   

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

Abstract: With the development of the society,the scale of data and networks are increasing rapidly.As one of the effective ways of studying network structure,community detecting is a significant issue in deep understanding of large scale networks.Based on the methods of non-overlapping community detecting in directed networks and overlapping community detecting in undirected networks,an overlapping community detecting algorithm in directed networks was proposed in this paper.The basic idea of this method is to divide a network according to two parameters:directed weight and belonging degree of nodes.The influences of these parameters on partition are discussed and the optimal parameters are obtained.The performance of the proposed algorithm was tested and compared with other algorithms on two real networks and one computer-generated network.Experimental results show that the algorithm presented in this paper is rather efficient to detect overlapping communities of directed network.

Key words: Directed networks,Community detection,Modularity,Overlapping community

[1] Rosvall M,Bergstrom T C.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences of the United States of America,2008,105(4):1118-1123
[2] Kernighan B W,Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970,49(2):291-307
[3] Barnes E R.An Algorithm for partitioning the nodes of a graph[J].SIAM J.Alg.Disc.Meth,1982,4(3):541-550
[4] 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,2001,99:7821-7826
[5] Leicht E A,Newman M E J.Community structure in directed networks[J].Physical Review Letters,2008,100(11):118703
[6] Newman M E J.Modularity and community structure in net-works[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582
[7] Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory and Experiment,2009:1742-5468
[8] Chauhan S,Girvan M,Ott E.A network function-based definition of communities in complex networks[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2012,22(3):033129
[9] Newman M E J.Community detection and graph partitioning[J].Europhys.Lett.,2013,3:28003
[10] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in larger networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,10:P10008
[11] Chen D B,Shang M S,Lv Z H,et al.Detecting overlapping communities of weighted networks via a local algorithm[J].Physica A:Statistical Mechanics and its Applications,2010,389(19):4177-4187
[12] Liu H T,Qin X,Yun H F,et al.A Community Detecting Algorithm in Directed Weighted Networks[J]. Lecture Notes in Electrical Engineering,2011,8:11-17
[13] 陈端兵,尚明生,李霞.重叠社区划分的两阶段策略[J].计算机科学,2013,40(1):225-228
[14] Newman M E J,Girvan M.Finding and evaluating communitystructure in networks[J].Physical Review E,2004,69(2):026113
[15] Leskovec J,Huttenlocher D,Kleinberg J.Predicting Positive and Negative Links in Online Social Networks [C]∥Proceedings of the 19th international conference on World Wide Web.ACM,2010:641-650
[16] Leskovec J,Kleinberg J,Faloutsos C.Graph evolution:Densification and shrinking diameters[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):2
[17] Ripeanu M,Foster I,Iamnitchi A.Mapping the Gnutella Network:Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design[J].IEEE Internet Computing Journal,2002,6:50-57
[18] Holme P,Saramki J.Temporal networks[J].Physics Reports,2012,519:97-125

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!