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
International Journal of Machine Learning and Cybernetics
Published in: International Journal of Machine Learning and Cybernetics 4/2019

20-11-2017 | Original Article

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

Authors: Xuegang Hu, Wei He, Lei Li, Yaojin Lin, Huizong Li, Jianhan Pan

Published in: International Journal of Machine Learning and Cybernetics | Issue 4/2019

Log in

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

search-config
loading …

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.
previous article Two-stage pruning method for gram-based categorical sequence clustering
next article Multi-criteria decision making based architecture selection for single-hidden layer feedforward neural networks

Dont have a licence yet? Then find out more about our products and how to get one 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

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"

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
Show more products
Literature
1.
2.
Wu X, Liu Z (2008) How community structure influences epidemic spread in social networks. Phys A 387(2):623–630CrossRef
3.
4.
Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106CrossRef
5.
Leung IX, Hui P, Lio P, Crowcroft J (2009) Towards real-time community detection in large networks. Phys Rev E 79.6:066107CrossRef
6.
Barber MJ, Clark JW (2009) Detecting network communities by propagating labels under constraints. Phys Rev E 80.2:026129CrossRef
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–4984CrossRef
8.
Liu X, Tsuyoshi M (2010) Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Phys A 389(7):1493–1500CrossRef
9.
Šubelj L, Bajec M (2011) Robust network community detection using balanced propagation. Eur Phys J B 81.3:353–362
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:036103MathSciNet
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:036103MathSciNetCrossRef
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):e27418CrossRef
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):e97021CrossRef
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 )CrossRef
18.
Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, CambridgeCrossRefMATH
19.
Shi L, Zhang J (2014) Community detection using robust label propagation algorithm. Sens Transducers 163(1):1726–5479
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–399CrossRef
22.
Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech 09:P09008
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:P03009MathSciNetCrossRef
25.
Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69.2:026113CrossRef
26.
Fortunato S, Barthélemy M (2007) Resolution limit in community detection. Proc Natl Acad Sci 104.1:36–41CrossRef
27.
Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci 105.4:1118–1123CrossRef
28.
Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78.4:046110CrossRef
29.
Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452–473CrossRef
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–405CrossRef
31.
32.
33.
Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’networks. Nature 393:440–442CrossRefMATH
34.
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–123MathSciNetCrossRefMATH
37.
Metadata
Title
An efficient and fast algorithm for community detection based on node role analysis
Authors
Xuegang Hu
Wei He
Lei Li
Yaojin Lin
Huizong Li
Jianhan Pan
Publication date
20-11-2017
Publisher
Springer Berlin Heidelberg
Published in
International Journal of Machine Learning and Cybernetics / Issue 4/2019
Print ISSN: 1868-8071
Electronic ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-017-0745-x

Other articles of this Issue 4/2019

International Journal of Machine Learning and Cybernetics 4/2019 Go to the issue

Original Article

The probabilistic ordered weighted continuous OWA operator and its application in group decision making

Original Article

Multi-criteria decision making based architecture selection for single-hidden layer feedforward neural networks

Original Article

Neighborhood attribute reduction: a multi-criterion approach

Original Article

Unsupervised feature selection based on self-representation sparse regression and local similarity preserving

Original Article

Hesitant interval neutrosophic linguistic set and its application in multiple attribute decision making

Original Article

A term correlation based semi-supervised microblog clustering with dual constraints