Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An efficient and fast algorithm for community detection based on node role analysis

  • Original Article
  • Published:
International Journal of Machine Learning and Cybernetics Aims and scope Submit manuscript

Abstract

The community structure of networks provides a comprehensive insight into their organizational structures and functional behaviors. Label propagation is one of the most commonly adopted community detection algorithm with nearly linear time complexity. It ignores the difference between nodes when breaking ties, leading to poor stability and the occurrence of the monster community. We note that different community-oriented node roles impact the label propagation in different ways. In this paper, we propose a role-based label propagation algorithm (roLPA), in which the heuristics with regard to community-oriented node role were used. We have evaluated the proposed algorithm on both real and artificial networks. The result shows that roLPA outperforms other state-of-the-art community detection algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99:7821–7826

    Article  MathSciNet  MATH  Google Scholar 

  2. Wu X, Liu Z (2008) How community structure influences epidemic spread in social networks. Phys A 387(2):623–630

    Article  Google Scholar 

  3. Fortunato S (2010) Community detection in graphs. Phys Rep 486(3):75–174

    Article  MathSciNet  Google Scholar 

  4. Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106

    Article  Google Scholar 

  5. Leung IX, Hui P, Lio P, Crowcroft J (2009) Towards real-time community detection in large networks. Phys Rev E 79.6:066107

    Article  Google Scholar 

  6. Barber MJ, Clark JW (2009) Detecting network communities by propagating labels under constraints. Phys Rev E 80.2:026129

    Article  Google Scholar 

  7. Tibély G, János K (2008) On the equivalence of the label propagation method of community detection and a Potts model approach. Phys A 387.19:4982–4984

    Article  Google Scholar 

  8. Liu X, Tsuyoshi M (2010) Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Phys A 389(7):1493–1500

    Article  Google Scholar 

  9. Šubelj L, Bajec M (2011) Robust network community detection using balanced propagation. Eur Phys J B 81.3:353–362

    Google Scholar 

  10. Šubelj L, Bajec M (2011) Unfolding communities in large complex networks: combining defensive and offensive label propagation for core extraction. Phys Rev E 83.3:036103

    MathSciNet  Google Scholar 

  11. Ugander J, Backstrom L (2013) Balanced label propagation for partitioning massive graphs. In: WSDM ACM

  12. Subelj L, Bajec M (2011) Unfolding communities in large complex networks: combining defensive and offensive label propagation for core extraction. Phys Rev E 83:036103

    Article  MathSciNet  Google Scholar 

  13. Scripps J, Tan PN, Esfahanian AH (2007) Node roles and community structure in networks. In: Joint 9th WEBKDD

  14. Chou BH, Suzuki E, Discovering community-oriented roles of nodes in a social network. DaWak (2010) 52–64

  15. Wang Y, Di Z, Fan Y (2011) Identifying and characterizing nodes important to community structure using the spectrum of the graph. PLoS One 6(11):e27418

    Article  Google Scholar 

  16. Zhu F, Wang W, Di Z, Fan Y (2014) Identifying and characterizing key nodes among communities based on electrical-circuit networks. PLoS One 9(6):e97021

    Article  Google Scholar 

  17. Huang S, Lv T, Zhang X, Yang Y, Zheng W, Wen C (2014) Identifying node role in social network based on multiple indicators. PLoS One 9:e103733 8 )

    Article  Google Scholar 

  18. Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  19. Shi L, Zhang J (2014) Community detection using robust label propagation algorithm. Sens Transducers 163(1):1726–5479

    Google Scholar 

  20. Zhao Y, Li S, Chen X (2012) Community detection using label propagation in entropic order. In: IEEE CIT

  21. Burt RS (2004) Structural holes and good ideas. Am J Sociol 110.2:349–399

    Article  Google Scholar 

  22. Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech 09:P09008

    Google Scholar 

  23. Zhang P (2015) A revisit to evaluating accuracy of community detection using the normalized mutual information. arXiv preprint 1501.03844

  24. Zhang J, Chen T, Hu J (2015) On the relationship between Gaussian stochastic blockmodels and label propagation algorithms. J Stat Mech 3:P03009

    Article  MathSciNet  Google Scholar 

  25. Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69.2:026113

    Article  Google Scholar 

  26. Fortunato S, Barthélemy M (2007) Resolution limit in community detection. Proc Natl Acad Sci 104.1:36–41

    Article  Google Scholar 

  27. Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci 105.4:1118–1123

    Article  Google Scholar 

  28. Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78.4:046110

    Article  Google Scholar 

  29. Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452–473

    Article  Google Scholar 

  30. Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav Ecol Sociobiol 54:396–405

    Article  Google Scholar 

  31. Girvan M, Newman MEJ (2002) Proc Natl Acad Sci 99:7821–7826

    Article  Google Scholar 

  32. Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74:036104

    Article  MathSciNet  Google Scholar 

  33. Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’networks. Nature 393:440–442

    Article  MATH  Google Scholar 

  34. Newman MEJ (2001) The structure of scientific collaboration networks. Proc Natl Acad Sci 98:404–409

    Article  MathSciNet  MATH  Google Scholar 

  35. Yang J, Leskovec J (2012) Defining and evaluating network communities based on ground-truth. In: ICDM

  36. Leskovec J, Lang K, Dasgupta A, Mahoney M (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29–123

    Article  MathSciNet  MATH  Google Scholar 

  37. Google programming contest (2002)

Download references

Acknowledgements

This research has been supported by the National 973 Program of China under Grant 2013CB329604, the Program for Changjiang Scholars and Innovative Research Team in University (PCSIRT) of the Ministry of Education, China, under Grant IRT13059, the National Natural Science Foundation of China (NSFC) under Grants 61503114 and 61229301, the Anhui Provincial Natural Science Foundation under grant 1408085QF130, and the Fundamental Research Funds for the Central Universities under Grant 2015HGCH0012.

Author information

Authors and Affiliations

  1. School of Computer and Information, Hefei University of Technology, Hefei, 230009, China

    Xuegang Hu, Wei He & Lei Li

  2. School of Computer Science, Minnan Normal University, Zhangzhou, 363000, China

    Yaojin Lin

  3. School of Economics and Management, Anhui University of Science and Technology, Huainan, 232001, China

    Huizong Li

  4. School of Computer Science and Technology, Jiangsu Normal University, Xuzhou, 221116, China

    Jianhan Pan

Authors
  1. Xuegang Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei He
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yaojin Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Huizong Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jianhan Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wei He.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hu, X., He, W., Li, L. et al. An efficient and fast algorithm for community detection based on node role analysis. Int. J. Mach. Learn. & Cyber. 10, 641–654 (2019). https://doi.org/10.1007/s13042-017-0745-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13042-017-0745-x

Keywords

Search

Navigation