×

Community detection in networks using new update rules for label propagation. (English) Zbl 1382.68184

Summary: Detecting community structure clarifies the link between structure and function in complex networks and is used for applications in many disciplines. The Label Propagation Algorithm (LPA) has the benefits of nearly-linear running time and easy implementation, but it returns multiple resulting partitions over multiple runs. Following LPA, some new updating rules are proposed to detect communities in networks, which are based mainly on the almost strong definition of communities and the topological similarity. Experiments on more artificial and real social networks have demonstrated better performance of the proposed method compared with that of the community detection algorithms CNM, Cfinder and MEP on the quality of communities.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C82 Small world graphs, complex networks (graph-theoretic aspects)
91D30 Social networks; opinion dynamics

Software:

GraphBase
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Porter MA, Onnela J-P, Mucha PJ (2009) Communities in networks. Not Am Math Soc 56:1082-1097, 1164-1166 · Zbl 1188.05142
[2] Strogatz SH (2001) Exploring complex networks. Nature 410:268-276 · Zbl 1370.90052 · doi:10.1038/35065725
[3] Xia Z, Bu Z (2012) Community detection based on a semantic network. Knowl Based Syst 26:30-39 · doi:10.1016/j.knosys.2011.06.014
[4] Fortunato S (2010) Community detection in graphs. Phys Rep 486:75 · doi:10.1016/j.physrep.2009.11.002
[5] Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435:814-818 · doi:10.1038/nature03607
[6] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D (2004) Defining and identifying clusters in networks. Proc Natl Acad Sci USA 101(9):2658-2663 · doi:10.1073/pnas.0400054101
[7] Bagrow J, Bolt E (2005) A local method for detecting communities. Phys Rev E 72:046108 · doi:10.1103/PhysRevE.72.046108
[8] Wu F, Huberman B (2004) Finding communities in linear time: a physics approach. Eur Phys J B 38:331-338 · doi:10.1140/epjb/e2004-00125-x
[9] Medus AD, Dorso CO (2009) Alternative approach to community detection in networks. Phys Rev E 79:066111 · doi:10.1103/PhysRevE.79.066111
[10] Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci USA 99:7821-7826 · Zbl 1032.91716 · doi:10.1073/pnas.122653799
[11] Clauset A, Newman MEJ, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111 · doi:10.1103/PhysRevE.70.066111
[12] Rosvall M, Bergstrom CT (2007) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci USA 105:1118-1123 · Zbl 1032.91716
[13] Ronhovde P, Nussinov Z (2010) Local resolution-limit-free Potts model for community detection. Phys Rev E 81:046114 · doi:10.1103/PhysRevE.81.046114
[14] Ball B, Karrer B, Newman MEJ (2011) Efficient and principled method for detecting communities in networks. Phys Rev E 84:036103 · doi:10.1103/PhysRevE.84.036103
[15] Rizman Žalik K, Žalik B (2014) A local multiresolution algorithm for detecting communities of unbalanced structures. Phys A Stat Mech Appl 407:380-393 · Zbl 1514.91162
[16] Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect communities in large-scale networks. Phys Rev E 76(3):036106 · doi:10.1103/PhysRevE.76.036106
[17] Barber MJ, Clark JW (2009) Detecting network communities by propagating labels under constraints. Phys Rev E 80:026129 · doi:10.1103/PhysRevE.80.026129
[18] Liu X, Murata T (2010) Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Phys A Stat Mech Appl 389(7):1493-1500 · doi:10.1016/j.physa.2009.12.019
[19] Schuetz P, Caflisch A (2008) Efficient modularity optimization by multistep greedy algorithm and node refinement. Phys Rev E 77:046112 · doi:10.1103/PhysRevE.77.046112
[20] Lancichinetti A, Fortunato S (2012) Consensus clustering in complex networks. Scientific Reports 2. Article number: 336
[21] This data are from Add Health, a program project by Udry J., Bearman S., Harris, Kathleen Mullan, and funded by a grant P01-HD31921 from the National Institute of Child Health and Human Development, Persons interested in obtaining data files from Add Health should contact Add Health, Carolina Population Center, (addhealth@unc.edu)
[22] Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452-473 · doi:10.1086/jar.33.4.3629752
[23] Arenas A, Díaz-Guilera A, Pérez-Vicente CJ (2006) Synchronization reveals topological scales in complex networks. Phys Rev Lett 96:114102 · Zbl 1112.34027
[24] Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110 · doi:10.1103/PhysRevE.78.046110
[25] Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing Community Structure Identification. J Stat Mech Theor Exp 2005(9). Article ID: P09008. doi:10.1088/1742-5468/2005/09/p0900
[26] 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 · doi:10.1007/s00265-003-0651-y
[27] Knuth DE (1993) The stanford graphbase: a platform for combinatorial computing. Addison-Wesley, Reading · Zbl 0806.68121
[28] Zardi H, Ben Romdhane L, MARS (Modeling of Automated Reasoning Systems) Research Group (2013) An O(n2) algorithm for detecting communities of unbalanced sizes in large scale social networks. Knowl Based Syst 37:19-36
[29] Ding C, Xiaofeng H (2001) Spectral min max cut for graph partitioning and data clustering, PhD thesis, California University
[30] Brandes U, Gaertler M (2003) Experiments on graph clustering algorithms, in 11. European Symposium on Algorithms, pp. 568-579
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.