License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.58
URN: urn:nbn:de:0030-drops-112731
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11273/
Go to the corresponding LIPIcs Volume Portal

Knierim, Charlotte ; Lengler, Johannes ; Pfister, Pascal ; Schaller, Ulysse ; Steger, Angelika

The Maximum Label Propagation Algorithm on Sparse Random Graphs

pdf-format:
LIPIcs-APPROX-RANDOM-2019-58.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{knierim_et_al:LIPIcs:2019:11273,
  author =	{Charlotte Knierim and Johannes Lengler and Pascal Pfister and Ulysse Schaller and Angelika Steger},
  title =	{{The Maximum Label Propagation Algorithm on Sparse Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11273},
  URN =		{urn:nbn:de:0030-drops-112731},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.58},
  annote =	{Keywords: random graphs, distributed algorithms, label propagation algorithms, consensus, community detection}
}

Keywords: random graphs, distributed algorithms, label propagation algorithms, consensus, community detection
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI