Document Open Access Logo

The Maximum Label Propagation Algorithm on Sparse Random Graphs

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.58.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Charlotte Knierim
  • ETH Zurich, Switzerland
Johannes Lengler
  • ETH Zurich, Switzerland
Pascal Pfister
  • ETH Zurich, Switzerland
Ulysse Schaller
  • ETH Zurich, Switzerland
Angelika Steger
  • ETH Zurich, Switzerland

Cite AsGet BibTex

Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller, and Angelika Steger. The Maximum Label Propagation Algorithm on Sparse Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.58

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
  • Theory of computation → Distributed algorithms
Keywords
  • random graphs
  • distributed algorithms
  • label propagation algorithms
  • consensus
  • community detection

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Michael J Barber and John W Clark. Detecting network communities by propagating labels under constraints. Physical Review E, 80(2):026129, 2009. Google Scholar
  2. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293-306, 2017. Google Scholar
  3. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 620-635. SIAM, 2016. Google Scholar
  4. Punam Bedi and Chhavi Sharma. Community detection in social networks. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 6(3):115-135, 2016. Google Scholar
  5. Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or comply? on breaking symmetry in consensus. arXiv preprint, 2017. URL: http://arxiv.org/abs/1702.04921.
  6. Andrea Clementi, Miriam Di Ianni, Giorgio Gambosi, Emanuele Natale, and Riccardo Silvestri. Distributed Community Detection in Dynamic Graphs. Theor. Comput. Sci., 584(C):19-41, June 2015. URL: https://doi.org/10.1016/j.tcs.2014.11.026.
  7. Colin Cooper, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga. Fast plurality consensus in regular expanders. arXiv preprint, 2016. URL: http://arxiv.org/abs/1605.08403.
  8. Gennaro Cordasco and Luisa Gargano. Label propagation algorithm: a semi-synchronous approach. International Journal of Social Network Mining, 1(1):3-26, 2012. Google Scholar
  9. Emilio Cruciani, Emanuele Natale, and Giacomo Scornavacca. On the Metastability of Quadratic Majority Dynamics on Clustered Graphs and its Biological Implications. CoRR, abs/1805.01406, 2018. URL: http://arxiv.org/abs/1805.01406.
  10. Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, and Horst Trinker. Efficient k-party voting with two choices. ArXiv e-prints, 2016. Google Scholar
  11. Uriel Feige, Michael Krivelevich, and Daniel Reichman. Contagious sets in random graphs. The Annals of Applied Probability, 27(5):2675-2697, 2017. Google Scholar
  12. Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 305-313. ACM, 2018. Google Scholar
  13. Mohsen Ghaffari and Merav Parter. A polylogarithmic gossip algorithm for plurality consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 117-126. ACM, 2016. Google Scholar
  14. Steve Gregory. Finding overlapping communities in networks by label propagation. New Journal of Physics, 12(10):103018, 2010. Google Scholar
  15. Steve Harenberg, Gonzalo Bello, L Gjeltema, Stephen Ranshous, Jitendra Harlalka, Ramona Seay, Kanchana Padmanabhan, and Nagiza Samatova. Community detection in large-scale networks: a survey and empirical evaluation. Wiley Interdisciplinary Reviews: Computational Statistics, 6(6):426-439, 2014. Google Scholar
  16. S. Janson, T. Łuczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. Google Scholar
  17. Kishore Kothapalli, Sriram V. Pemmaraju, and Vivek Sardeshmukh. On the Analysis of a Label Propagation Algorithm for Community Detection. In Distributed Computing and Networking, pages 255-269, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  18. Ian XY Leung, Pan Hui, Pietro Lio, and Jon Crowcroft. Towards real-time community detection in large networks. Physical Review E, 79(6):066107, 2009. Google Scholar
  19. Elchanan Mossel and Omer Tamuz. Opinion exchange dynamics. Probability Surveys, 14:155-204, 2017. Google Scholar
  20. Svatopluk Poljak and Miroslav Sŭra. On periodical behaviour in societies with symmetric influences. Combinatorica, 3(1):119-121, 1983. Google Scholar
  21. Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3):036106, 2007. Google Scholar
  22. Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001. Google Scholar
  23. Zhao Yang, René Algesheimer, and Claudio J Tessone. A comparative analysis of community detection algorithms on artificial networks. Scientific Reports, 6:30750, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact