Dynamic community detection in evolving networks using locality modularity optimization

详细信息    查看全文

• 作者：Mário Cordeiro ; Rui Portocarrero Sarmento ; João Gama
• 关键词：Dynamic community detection ; Large ; scale networks analysis ; Modularity ; Evolving networks
• 刊名：Social Network Analysis and Mining
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：6
• 期：1
• 全文大小：1,731 KB
• 参考文献：1.Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of community hierarchies in large networks. CoRR abs/0803.0476
  2.Chen M, Nguyen T, Szymanski B (2013) On measuring the quality of a network community structure. In: Social computing (SocialCom), 2013 international conference on, pp 122–127. doi:10.​1109/​SocialCom.​ 25
  3.Chen M, Nguyen T, Szymanski BK (2015) A new metric for quality of network community structure. CoRR abs/1507.04308. arXiv:​1507.​04308
  4.Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174. doi:10.​1016/​j.​physrep.​2009.​11.​002 MathSciNet CrossRef
  5.Fortunato S, Barthelemy M (2007) Resolution limit in community detection. In: Proceedings of the national academy of sciences. http://​www.​pnas.​org/​cgi/​content/​abstract/​104/​1/​36
  6.Greene D, Doyle D, Cunningham P (2010) Tracking the evolution of communities in dynamic social networks. In: ASONAM, pp 176–183. IEEE computer society, Washington, DC. doi:10.​1109/​ASONAM.​2010.​17
  7.Greene D, Doyle D, Cunningham P (2010) Tracking the evolution of communities in dynamic social networks. In: Proceedings–2010 international conference on advances in social network analysis and mining, ASONAM 2010, pp 176–183. doi:10.​1109/​ASONAM.​2010.​17
  8.Haynes J, Perisic I (2009) Mapping search relevance to social networks. In: Proceedings of the 3rd workshop on social network mining and analysis, SNA-KDD ’09, pp 2:1–2:7. ACM, New York, NY. doi:10.​1145/​1731011.​1731013
  9.Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining–KDD ’05, p. 177. ACM Press, New York. doi:10.​1145/​1081870.​1081893
  10.Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2), 026,113+. doi:10.​1103/​physreve.​69.​026113
  11.Nguyen NP, Dinh TN, Tokala S, Thai MT (2011) Overlapping communities in dynamic networks: their detection and mobile applications. In: P. Ramanathan T, Nandagopal BN, Levine (eds) Proceedings of the 17th annual international conference on mobile computing and networking, MOBICOM 2011, Las Vegas, Nevada, September 19–23, pp 85–96. ACM. doi:10.​1145/​2030613.​2030624
  12.Nguyen NP, Dinh TN, Xuan Y, Thai MT (2011) Adaptive algorithms for detecting community structure in dynamic social networks. In: INFOCOM, pp 2282–2290. IEEE
  13.Palla G, Barabasi AL, Vicsek T (2007) Quantifying social group evolution. Nature 446(7136):664–667. doi:10.​1038/​nature05670 CrossRef
  14.Pujol JM, Erramilli V, Rodriguez P (2009) Divide and conquer: partitioning online social networks. CoRR abs/0905.4918
  15.Shang J, Liu L, Xie F, Chen Z, Miao J, Fang X, Wu C (2012) A real-time detecting algorithm for tracking community structure of dynamic networks. SNAKDD, 18th ACM SIGKDD 12
  16.Xie J, Chen M, Szymanski BK (2013) LabelRankT: incremental community detection in dynamic networks via label propagation
  17.Xie J, Kelley S, Szymanski B (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv (CSUR). doi:10.​1145/​2501654.​2501657 MATH
  18.Xie J, Szymanski B (2013) Labelrank: a stabilized label propagation algorithm for community detection in networks. Network Science Workshop (NSW)
  19.Xie J, Szymanski BK (2012) Towards linear time overlapping community detection in social networks. In: Lecture notes in computer science, vol 7301 LNAI, pp 25–36
  20.Xie J, Szymanski BK, Liu X (2011) SLPA: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: IEEE international conference on data mining, ICDM, pp 344–349
  21.Ye Z, Hu S, Yu J (2008) Adaptive clustering algorithm for community detection in complex networks. Phys. Rev E 78, 046,115. doi:10.​1103/​PhysRevE.​78.​046115
  
• 作者单位：Mário Cordeiro (1)
  Rui Portocarrero Sarmento (2)
  João Gama (2)
  
  1. FEUP, Porto University, R. Dr. Roberto Frias s/n, 4200-465, Porto, Portugal
  2. LIAAD - INESC TEC, FEP, Porto University, R. Dr. Roberto Frias 378, 4200-465, Porto, Portugal
  
• 刊物类别：Computer Science
• 刊物主题：Sociology
  Data Mining and Knowledge Discovery
  Theoretical Ecology
  Game Theory
  
• 出版者：Springer Wien
• ISSN：1869-5469

文摘

The amount and the variety of data generated by today’s online social and telecommunication network services are changing the way researchers analyze social networks. Facing fast evolving networks with millions of nodes and edges are, among other factors, its main challenge. Community detection algorithms in these conditions have also to be updated or improved. Previous state-of-the-art algorithms based on the modularity optimization (i.e. Louvain algorithm), provide fast, efficient and robust community detection on large static networks. Nonetheless, due to the high computing complexity of these algorithms, the use of batch techniques in dynamic networks requires to perform network community detection for the whole network in each one of the evolution steps. This fact reveals to be computationally expensive and unstable in terms of tracking of communities. Our contribution is a novel technique that maintains the community structure always up-to-date following the addition or removal of nodes and edges. The proposed algorithm performs a local modularity optimization that maximizes the modularity gain function only for those communities where the editing of nodes and edges was performed, keeping the rest of the network unchanged. The effectiveness of our algorithm is demonstrated with the comparison to other state-of-the-art community detection algorithms with respect to Newman’s Modularity, Modularity with Split Penalty, Modularity Density, number of detected communities and running time.