King's College London

Research portal

Eigenvector computation and community detection in asynchronous gossip models

Research output: Contribution to journalConference paper

Frederik Mallmann-Trenn, Cameron Musco, Christopher Musco

Original languageEnglish
JournalLeibniz International Proceedings in Informatics, LIPIcs
Published1 Jul 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: 9 Jul 201813 Jul 2018

King's Authors

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.

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454