Abstract
Label propagation has proven to be an extremely fast method for detecting communities in large complex networks. Furthermore, due to its simplicity, it is also currently one of the most commonly adopted algorithms in the literature. Despite various subsequent advances, an important issue of the algorithm has not yet been properly addressed. Random (node) update orders within the algorithm severely hamper its robustness, and consequently also the stability of the identified community structure. We note that an update order can be seen as increasing propagation preferences from certain nodes, and propose a balanced propagation that counteracts for the introduced randomness by utilizing node balancers. We have evaluated the proposed approach on synthetic networks with planted partition, and on several real-world networks with community structure. The results confirm that balanced propagation is significantly more robust than label propagation, when the performance of community detection is even improved. Thus, balanced propagation retains high scalability and algorithmic simplicity of label propagation, but improves on its stability and performance.
Similar content being viewed by others
References
M. Girvan, M.E.J. Newman, P. Natl. Acad. Sci. USA 99, 7821 (2002)
G. Palla, I. Derényi, I. Farkas, T. Vicsek, Nature 435, 814 (2005)
A. Arenas, A. Díaz-Guilera, C.J. Pérez-Vicente, Phys. Rev. Lett. 96, 114102 (2006)
A. Clauset, M.E.J. Newman, C. Moore, Phys. Rev. E 70, 066111 (2004)
F. Wu, B.A. Huberman, Eur. Phys. J. B 38, 331 (2004)
S. Son, H. Jeong, J.D. Noh, Eur. Phys. J. B 50, 431 (2006)
U.N. Raghavan, R. Albert, S. Kumara, Phys. Rev. E 76, 036106 (2007)
G. Agarwal, D. Kempe, Eur. Phys. J. B 66, 409 (2008)
V.D. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre, J. Stat. Mech. P10008 (2008)
M. Rosvall, C.T. Bergstrom, P. Natl. Acad. Sci. USA 105, 1118 (2008)
J. Liu, Eur. Phys. J. B 77, 547 (2010)
P. Ronhovde, Z. Nussinov, Phys. Rev. E 81, 046114 (2010)
L. Subelj, M. Bajec, Phys. Rev. E 83, 036103 (2011)
S. Fortunato, Phys. Rep. 486, 75 (2010)
Y. Hu, H. Chen, P. Zhang, M. Li, Z. Di, Y. Fan, Phys. Rev. E 78, 026121 (2008)
G. Tibély, J. Kertész, Physica A 387, 4982 (2008)
M.J. Barber, J.W. Clark, Phys. Rev. E 80, 026129 (2009)
I.X.Y. Leung, P. Hui, P. Liò, J. Crowcroft, Phys. Rev. E 79, 066107 (2009)
X. Liu, T. Murata, Physica A 389, 1493 (2009)
X. Liu, T. Murata, Community detection in large-scale bipartite networks, in Proceedings of the International Conference on Web Intelligence and Intelligent Agent Technology (2009), Vol. 1, pp. 50–57
S. Pang, C. Chen, T. Wei, A realtime clique detection algorithm: Time-based incremental label propagation, in Proceedings of the International Conference on Intelligent Information Technology Application (2009), Vol. 3, pp. 459–462
C. Pang, F. Shao, R. Sun, S. Li, Detecting community structure in networks by propagating labels of nodes, in Proceedings of the International Symposium on Neural Networks (2009), pp. 839–846
S. Gregory, New J. Phys. 12, 103018 (2010)
X. Liu, T. Murata, Evaluating community structure in bipartite networks, in Proceedings of the IEEE International Conference on Social Computing (2010), pp. 576–581
L. Subelj, M. Bajec, Unfolding network communities by combining defensive and offensive label propagation, in Proceedings of the ECML PKDD Workshop on the Analysis of Complex Networks (2010), pp. 87–104
Q. Ye, B. Wu, Y. Gao, B. Wang, Detecting communities in massive networks based on local community attractive force optimization, in Proceedings of the International Conference on Advances in Social Networks Analysis and Mining (2010), pp. 291–295
L. Freeman, Sociometry 40, 35 (1977)
L.C. Freeman, Soc. Networks 1, 215 (1979)
D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998)
F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, P. Natl. Acad. Sci. USA 101, 2658 (2004)
A. Strehl, J. Ghosh, J. Mach. Learn. Res. 3, 583 (2002)
M.E.J. Newman, M. Girvan, Phys. Rev. E 69, 026113 (2004)
S. Fortunato, M. Barthelemy, P. Natl. Acad. Sci. USA 104, 36 (2007)
J. Kumpula, J. Saramäki, K. Kaski, J. Kertész, Eur. Phys. J. B 56, 5 (2007)
B.H. Good, Y.A. de Montjoye, A. Clauset, Phys. Rev. E 81, 046106 (2010)
B. Bollobás, Modern graph theory (Springer, 1998)
J. Leskovec, K.J. Lang, A. Dasgupta, M.W. Mahoney, Internet Mathematics 6, 29 (2009)
D.J.C. MacKay, Information theory, inference, and learning algorithms (Cambridge University Press, 2003)
L. Danon, A. Díaz-Guilera, J. Duch, A. Arenas, J. Stat. Mech. P09008 (2005)
M. Meila, J. Multivar. Anal. 98, 873 (2007)
B. Karrer, E. Levina, M.E.J. Newman, Phys. Rev. E 77, 046119 (2008)
A. Lancichinetti, S. Fortunato, F. Radicchi, Phys. Rev. E 78, 046110 (2008)
A.L. Barabási, R. Albert, Science 286, 509 (1999)
M.E.J. Newman, Eur. Phys. J. B 38, 321 (2004)
A. Lancichinetti, S. Fortunato, Phys. Rev. E 80, 056117 (2009)
P. Erdős, A. Rényi, Publ. Math. Debrecen 6, 290 (1959)
W.W. Zachary, J. Anthropol. Res. 33, 452 (1977)
D. Lusseau, K. Schneider, O.J. Boisseau, P. Haase, E. Slooten, S.M. Dawson, Behav. Ecol. Sociobiol. 54, 396 (2003)
V. Krebs, A network of co-purcheased books about U.S. politics (2008), http://www.orgnet.com/
P. Gleiser, L. Danon, Adv. Compl. Syst. 6, 565 (2003)
H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, A. Barabási, Nature 407, 651 (2000)
M.E.J. Newman, Phys. Rev. E 74, 036104 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Šubelj, L., Bajec, M. Robust network community detection using balanced propagation. Eur. Phys. J. B 81, 353–362 (2011). https://doi.org/10.1140/epjb/e2011-10979-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1140/epjb/e2011-10979-2