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

    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

    Keywords

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

    ASJC Scopus subject areas

    • Software

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

    Cite this