Eigenvector computation and community detection in asynchronous gossip models

Frederik Mallmann-Trenn, Cameron Musco, Christopher Musco

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We give a simple distributed algorithm for computing adjacency matrix eigenvectors for the communication graph in an asynchronous gossip model. We show how to use this algorithm to give state-of-the-art asynchronous community detection algorithms when the communication graph is drawn from the well-studied stochastic block model. Our methods also apply to a natural alternative model of randomized communication, where nodes within a community communicate more frequently than nodes in di erent communities. Our analysis simplifies and generalizes prior work by forging a connection between asynchronous eigenvector computation and Oja's algorithm for streaming principal component analysis. We hope that our work serves as a starting point for building further connections between the analysis of stochastic iterative methods, like Oja's algorithm, and work on asynchronous and gossip-type algorithms for distributed computation.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
DOIs
StatePublished - Jul 1 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume107
ISSN (Print)1868-8969

Other

Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
CountryCzech Republic
CityPrague
Period7/9/187/13/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Block model
  • Community detection
  • Distributed clustering
  • Eigenvector computation
  • Gossip algorithms
  • Population protocols

Fingerprint Dive into the research topics of 'Eigenvector computation and community detection in asynchronous gossip models'. Together they form a unique fingerprint.

Cite this