Show simple item record

dc.contributor.author
Knierim, Charlotte
dc.contributor.author
Lengler, Johannes
dc.contributor.author
Pfister, Pascal
dc.contributor.author
Schaller, Ulysse
dc.contributor.author
Steger, Angelika
dc.contributor.editor
Achlioptas, Dimitris
dc.contributor.editor
Végh, László A.
dc.date.accessioned
2019-10-14T07:13:28Z
dc.date.available
2019-10-12T04:22:09Z
dc.date.available
2019-10-14T07:11:53Z
dc.date.available
2019-10-14T07:13:28Z
dc.date.issued
2019
dc.identifier.isbn
978-3-95977-125-2
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.APPROX-RANDOM.2019.58
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/370194
dc.identifier.doi
10.3929/ethz-b-000370194
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Random graphs
en_US
dc.subject
Distributed algorithms
en_US
dc.subject
Label propagation algorithms
en_US
dc.subject
Consensus
en_US
dc.subject
Community detection
en_US
dc.title
The Maximum Label Propagation Algorithm onSparse Random Graphs
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
145
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
58
en_US
ethz.size
15 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
International Conference on Approximation Algorithms for Combinatorial Optimization Problems and International Conference on Randomization and Computation (APPROX/RANDOM 2019)
en_US
ethz.event.location
Cambridge, MA, USA
en_US
ethz.event.date
September 20-22, 2019
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
ethz.date.deposited
2019-10-12T04:22:19Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-10-14T07:12:06Z
ethz.rosetta.lastUpdated
2024-02-02T09:34:14Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=The%20Maximum%20Label%20Propagation%20Algorithm%20onSparse%20Random%20Graphs&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2019&rft.volume=145&rft.spage=58&rft.issn=1868-8969&rft.au=Knierim,%20Charlotte&Lengler,%20Johannes&Pfister,%20Pascal&Schaller,%20Ulysse&Steger,%20Angelika&rft.isbn=978-3-95977-125-2&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.APPROX-RANDOM.2019.58&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record