Community detection with the Label Propagation Algorithm: A survey

• Published in: Physica A 2019-11, Vol.534, p.122058, Article 122058
• Main Authors: Garza, Sara E., Schaeffer, Satu Elisa
• Format: Article
• Language: English
• Subjects: Community detection; Graph clustering; Label Propagation Algorithm; LPA
• ISSN: 0378-4371; 1873-2119
• DOI: 10.1016/j.physa.2019.122058

Community detection aims at discovering the structure, behavior, dynamics, and organization of a complex network by finding cohesive groups where nodes (entities) are, in some sense, more similar within the group and groups are in some fashion separated from the other groups. The Label Propagation Algorithm (LPA), which mimics epidemic contagion by spreading labels, is a popular algorithm for this task. Its variants (enhancements, extensions, combinations) seek to improve or to adapt it while preserving the advantages of the original formulation. This survey gathers, classifies, and summarizes LPA-related advances from 2007 to mid 2019. We also experiment with combinations of numerous LPA “building blocks” on two types of small synthetic networks; essentially all of the 13,834 resulting LPA variants have their niche in terms of either higher solution quality or lower computational load with acceptable quality, but none is universally superior. •The Label Propagation Algorithm (LPA) has caught attention for its advantages.•Abundant literature finds LPA efficient, scalable, conceptually clear, and simple.•We review LPA-related proposals, including enhancements and extensions.•An empirical study of 13,834 variants of LPA is presented.•Experiments indicate that most enhancements are beneficial in specific scenarios.