2026-07-24T14:51:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9163 2024-03-06T10:43:31Z ddc:004 open_access

Eigenvector Computation and Community Detection in Asynchronous Gossip Models Mallmann-Trenn, Frederik Musco, Cameron Musco, Christopher block model community detection distributed clustering eigenvector computation gossip algorithms population protocols 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 different 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frederik Mallmann-Trenn and Cameron Musco and Christopher Musco 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.159 urn:nbn:de:0030-drops-91639 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.159 eng https://creativecommons.org/licenses/by/3.0/legalcode