The Maximum Label Propagation Algorithm onSparse Random Graphs
OPEN ACCESS
Loading...
Author / Producer
Date
2019
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli et al., 2013] it was also conjectured that the same result still holds for sparse graphs if the degrees are at least C log n. We disprove this conjecture by showing that even for degrees n^epsilon, for some epsilon>0, the algorithm converges without reaching consensus. In fact, we show that the algorithm does not even reach almost consensus, but converges prematurely resulting in orders of magnitude more communities.
Permanent link
Publication status
published
Book title
Volume
145
Pages / Article No.
58
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
International Conference on Approximation Algorithms for Combinatorial Optimization Problems and International Conference on Randomization and Computation (APPROX/RANDOM 2019)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Random graphs; Distributed algorithms; Label propagation algorithms; Consensus; Community detection
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)