Network Analysis; Graph theory; Community detection
Résumé :
[en] The objective of a community detection algorithm is to group
similar nodes in a network into communities, while increasing the dis-
similarity between them. Several methods have been proposed but many
of them are not suitable for large-scale networks because they have high
complexity and use global knowledge. The Label Propagation Algorithm
(LPA) assigns a unique label to every node and propagates the labels
locally, while applying the majority rule to reach a consensus. Nodes
which share the same label are then grouped into communities. Although
LPA excels with near linear execution time, it gets easily stuck in local
optima and often returns a single giant community. To overcome these
problems we propose MemLPA, a novel LPA where each node imple-
ments memory and the decision rule takes past states of the network
into account. We demonstrate through extensive experiments on the
Lancichinetti-Fortunato-Radicchi benchmark and a set of real-world net-
works that MemLPA outperforms most of state-of-the-art community
detection algorithms.
Centre de recherche :
- Luxembourg Centre for Contemporary and Digital History (C2DH) > Digital History & Historiography (DHI) - Luxembourg Centre for Contemporary and Digital History (C2DH) > Doctoral Training Unit (DTU)
Disciplines :
Sciences informatiques
Auteur, co-auteur :
FISCARELLI, Antonio Maria ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
BRUST, Matthias R. ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
DANOY, Grégoire ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
BOUVRY, Pascal ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Co-auteurs externes :
no
Langue du document :
Anglais
Titre :
A Memory-Based Label Propagation Algorithm for Community Detection
Albert, R., Jeong, H., Barabási, A.L.: Internet: Diameter of the world-wide web. Nature 401(6749), 130–131 (1999)
Barber, M.J., Clark, J.W.: Detecting network communities by propagating labels under constraints. Phys. Rev. E 80(2) (2009)
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech.: Theory Exp. 2008(10) (2008)
Brandes, U., et al.: On modularity clustering. IEEE Trans. Knowl. Data Eng. 20(2), 172–188 (2008)
Clauset, A., Newman, M.E., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6) (2004)
Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJournal Complex Syst. (2006). http://igraph.org
Danon, L., Diaz-Guilera, A., Duch, J., Arenas, A.: Comparing community structure identification. J. Stat. Mech.: Theory Exp. 2005(09), P09008 (2005)
Dongen, S.: A Cluster Algorithm for Graphs (2000)
Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)
Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., Barabási, A.L.: The large-scale organization of metabolic networks. Nature 407(6804), 651–654 (2000)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)
Leung, I.X., Hui, P., Lio, P., Crowcroft, J.: Towards real-time community detection in large networks. Phys. Rev. E 79(6), 066107 (2009)
Liu, X., Murata, T.: Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Phys. A Stat. Mech. 389(7), 1493–1500 (2010)
Newman, M.E.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006)
Newman, M.E., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)
Orman, G.K., Labatut, V., Cherifi, H.: Comparative evaluation of community detection algorithms: a topological approach. J. Stat. Mech. Theory Exp. 2012(08), P08001 (2012)
Pons, P., Latapy, M.: Computing communities in large networks using random walks. In: ISCIS, vol. 3733, pp. 284–293 (2005)
Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)
Filho, R.J., Brust, M.R., Ribeiro, C.H.: Consensus dynamics in a non-deterministic naming game with shared memory. arXiv preprint arXiv:0912.4553 (2009)
Reichardt, J., Bornholdt, S.: Statistical mechanics of community detection. Phys. Rev. E 74(1), 016110 (2006)
Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. 105(4), 1118–1123 (2008)
Scott, J.: Social Network Analysis. Sage, California (2017)
Šubelj, L., Bajec, M.: Unfolding communities in large complex networks: combining defensive and offensive label propagation for core extraction. Phys. Rev. E 83(3) (2011)
Uzun, T.G., Da Silva-Filho, R.J., Brust, M.R., Ribeiro, C.H.: Influence of shared memory and network topology in the consensus dynamics of a naming game. http://dimap.ufrn.br/csbc2011/anais/eventos/contents/SEMISH/SemishSessao1Artigo3Uzun.pdf
Xie, J., Szymanski, B.K.: Labelrank: A stabilized label propagation algorithm for community detection in networks. In: Network Science Workshop (NSW). IEEE (2013)
Xie, J., Szymanski, B.K.: Community detection using a neighborhood strength driven label propagation algorithm. arXiv preprint arXiv:1105.3264 (2011)
Xie, J., Szymanski, B.K., Liu, X.: Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: Data Mining Workshops (ICDMW). IEEE (2011)
Yang, Z., Algesheimer, R., Tessone, C.J.: A comparative analysis of community detection algorithms on artificial networks. Sci. Rep. 6, 30750 (2016)
