Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Computing
Published in: Computing 10/2020

07-08-2020 | Regular Paper

Improved label propagation algorithm for overlapping community detection

Author: Shi Dong

Published in: Computing | Issue 10/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Community detection plays an important role in the analysis of complex networks. However, overlapping community detection in real networks is still a challenge. To address the problems of pre-input parameters and label redundancy, an improved label propagation algorithm (ILPA) that adopts a method based on the influence factor is proposed in this paper. Theoretical analysis and experimental results on both synthetic and real datasets show that the ILPA detects that the overlapping community has higher accuracy compared to other existing methods.
previous article POF-SVLM: pareto optimized framework for seamless VM live migration
next article Performance analysis of the ubiquitous and emergent properties of an autonomic reflective middleware for smart cities

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
2.
Huang J, Sun H, Liu Y, Song Q, Weninger T (2011) Towards online multiresolution community detection in large-scale networks. PLoS ONE 6(8):e23829
3.
Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv (csur) 45(4):43MATH
4.
Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106
5.
Barber MJ, Clark JW (2009) Detecting network communities by propagating labels under constraints. Phys Rev E 80(2):026129
6.
Liu X, Murata T (2010) Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A Stat Mech Appl 389(7):1493–1500
7.
Palla G, Dernyi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435:814–818
8.
Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phys 12(10):103018
9.
Xie J, Szymanski BK, Liu X (2011) Slpa: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: 2011 IEEE 11th international conference on data mining workshops. IEEE, pp 344–349
10.
He-Li S, Jian-Bin H, Yong-Qiang T, Qin-Bao S, Huai-Liang L (2015) Detecting overlapping communities in networks via dominant label propagation. Chin Phys B 24(1):018703
11.
Chakrabarti D, Kumar R, Tomkins A (2006) Evolutionary clustering. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 554–560
12.
Chi Y, Song X, Zhou D, Hino K, Tseng BL (2007) Evolutionary spectral clustering by incorporating temporal smoothness. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 153–162
13.
Lin Y-R, Chi Y, Zhu S, Sundaram H, Tseng BL (2008) Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In: Proceedings of the 17th international conference on World Wide Web. ACM, pp 685–694
14.
Kim M-S, Han J (2009) A particle-and-density based evolutionary clustering method for dynamic networks. Proc VLDB Endow 2(1):622–633
15.
Nguyen NP, Dinh TN, Tokala S, Thai MT (2011) Overlapping communities in dynamic networks: their detection and mobile applications. In: Proceedings of the 17th annual international conference on mobile computing and networking. ACM, pp 85–96
16.
Cazabet R, Amblard F, Hanachi C (2010) Detection of overlapping communities in dynamical social networks. In: 2010 IEEE second international conference on social computing (SocialCom). IEEE, pp 309–314
17.
Tang L, Liu H, Zhang J, Nazeri Z (2008) Community evolution in dynamic multi-mode networks. In: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 677–685
18.
Yang T, Chi Y, Zhu S, Gong Y, Jin R (2011) Detecting communities and their evolutions in dynamic social networksa Bayesian approach. Mach Learn 82(2):157–189MathSciNetMATH
19.
Gupta M, Aggarwal CC, Han J, Sun Y (2001) Evolutionary clustering and analysis of bibliographic networks. In: 2011 International conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 63–70
20.
Tantipathananandh C, Berger-Wolf TY (2011) Finding communities in dynamic social networks. In: 2011 IEEE 11th international conference on data mining. IEEE, pp 1236–1241
21.
Li Y, He K, Kloster K, Bindel D, Hopcroft J (2018) Local spectral clustering for overlapping community detection. ACM Trans Knowl Discov Data 12(2):17:1–17:27
22.
Shi P, He K, Bindel D, Hopcroft JE (2019) Locally-biased spectral approximation for community detection. Knowl Based Syst 164:459–472
23.
24.
Chin JH, Ratnavelu KA (2017) Semi-synchronous label propagation algorithm with constraints for community detection in complex networks. Sci Rep 7:45836
25.
Xu M, Li Y, Li R, Zou F, Gu X (2019) Eadp: an extended adaptive density peaks clustering for overlapping community detection in social networks. Neurocomputing 337:287–302
26.
Chakraborty T, Ghosh S, Park N (2019) Ensemble-based overlapping community detection using disjoint community structures. Knowl Based Syst 163:241–251
27.
Newman ME (2004) Detecting community structure in networks. Eur Phys J B Condens Matter Complex Syst 38(2):321–330
28.
Lü L, Zhang Y-C, Yeung CH, Zhou T (2011) Leaders in social networks, the delicious case. PLoS ONE 6(6):e21202
29.
Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110
30.
Lusseau D (2003) The emergent properties of a dolphin social network. Proc R Soc Lond B Biol Sci 270(Suppl 2):S186–S188
31.
Lusseau D, Newman ME (2004) Identifying the role that animals play in their social networks. Proc R Soc Lond B Biol Sci 271(Suppl 6):S477–S481
32.
Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452–473
33.
Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826MathSciNetMATH
34.
Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033015
35.
Nicosia V, Mangioni G, Carchiolo V, Malgeri M (2009) Extending the definition of modularity to directed graphs with overlapping communities. J Stat Mech Theory Exp 2009(03):P03024MATH
36.
Shen H, Cheng X, Cai K, Hu M-B (2009) Detect overlapping and hierarchical community structure in networks. Physica A Stat Mech Appl 388(8):1706–1712
Metadata
Title
Improved label propagation algorithm for overlapping community detection
Author
Shi Dong
Publication date
07-08-2020
Publisher
Springer Vienna
Published in
Computing / Issue 10/2020
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI
https://doi.org/10.1007/s00607-020-00836-3

Other articles of this Issue 10/2020

Computing 10/2020 Go to the issue

Regular Paper

IoT streaming data integration from multiple sources

Regular Paper

Performance analysis of the ubiquitous and emergent properties of an autonomic reflective middleware for smart cities

Regular Paper

POF-SVLM: pareto optimized framework for seamless VM live migration

Regular Paper

Gravitational search algorithm based on multiple adaptive constraint strategy

Regular Paper

Constraint aware profit maximization scheduling of tasks in heterogeneous datacenters

Regular Paper

An approach to evaluate trust and reputation of things in a Multi-IoTs scenario

Premium Partner

    Image Credits