Paper published in a book (Scientific congresses, symposiums and conference proceedings)
A Memory-Based Label Propagation Algorithm for Community Detection
Fiscarelli, Antonio Maria; Brust, Matthias R.; Danoy, Grégoire et al.
2018In Aiello, Luca Maria; Cherifi, Chantal; Cherifi, Hocine et al. (Eds.) Complex Networks and Their Applications VII
Peer reviewed
 

Files


Full Text
A Memory-Based Label Propagation Algorithm for Community Detection Antonio Maria Fiscarelli, Matthias R. Brust, Grégoire Danoy, and Pascal Bouvry.pdf
Author postprint (486.6 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Network Analysis; Graph theory; Community detection
Abstract :
[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.
Research center :
- 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 :
Computer science
Author, co-author :
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)
External co-authors :
no
Language :
English
Title :
A Memory-Based Label Propagation Algorithm for Community Detection
Publication date :
02 December 2018
Event name :
COMPLEX NETWORKS
Event place :
Cambridge, United Kingdom
Event date :
from 11-12-2018 to 13-12-2018
Audience :
International
Main work title :
Complex Networks and Their Applications VII
Author, co-author :
Aiello, Luca Maria
Cherifi, Chantal
Cherifi, Hocine
Lambiotte, Renaud
Pietro, Liò
Rocha, Luis M.
Publisher :
Springer, Cham, Switzerland
Edition :
7
ISBN/EAN :
978-3-030-05410-6
Pages :
171-182
Peer reviewed :
Peer reviewed
Focus Area :
Computational Sciences
FnR Project :
FNR10929115 - Digital History And Hermeneutics, 2015 (01/03/2017-31/08/2023) - Andreas Fickers
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 20 January 2019

Statistics


Number of views
205 (65 by Unilu)
Number of downloads
311 (11 by Unilu)

Scopus citations®
 
6
Scopus citations®
without self-citations
3

Bibliography


Similar publications



Contact ORBilu