Find Your Place: Simple Distributed Algorithms for Community Detection

DOI10.1137/19M1243026MaRDI QIDQ5115703zbMATH OpenOpenAlexFDO

Authors Luca Becchetti, Francesco Pasquale, Luca Trevisan, Andrea Clementi, Emanuele Natale

Publication date 18 August 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03927

zbMATH Keywords

community detectionstochastic block modelsspectral analysisdistributed algorithmsaveraging dynamics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Abstract: Given an underlying graph, we consider the following emph{dynamics}: Initially, each node locally chooses a value in $-1,1$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting.

Recommendations

• Find your place: simple distributed algorithms for community detection
• Distributed community detection in dynamic graphs
• A distributed community detection algorithm for large scale networks under stochastic block models
• Distributed Community Detection in Dynamic Graphs
• COMMUNITY FINDING IN COMPLEX NETWORKS
• Detecting network communities: a new systematic and efficient algorithm

Cites work

• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 2061729 (Why is no real title available?)
• scientific article; zbMATH DE number 878889 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 3070747 (Why is no real title available?)
• A biological solution to a fundamental distributed computing problem
• A decentralized algorithm for spectral analysis
• A proof of the block model threshold conjecture
• A simple population protocol for fast robust approximate majority
• A simplified neuron model as a principal component analyzer
• A spectral heuristic for bisecting random graphs
• An optimal bit complexity randomized distributed MIS algorithm
• Approximating the Permanent
• Authoritative sources in a hyperlinked environment
• Average whenever you meet: opportunistic protocols for community detection
• Belief propagation, robust reconstruction and optimal recovery of block models
• Broadcast Gossip Algorithms for Consensus
• Community detection and stochastic block models: recent developments
• Community detection thresholds and the weak Ramanujan property
• Concentration and regularization of random graphs
• Convergence speed in distributed consensus and averaging
• Distributed average consensus with least-mean-square deviation
• Distributed probabilistic polling and applications to proportionate agreement
• Eigenvector Computation and Community Detection in Asynchronous Gossip Models
• Exact Recovery in the Stochastic Block Model
• Expander graphs and their applications
• Find your place: simple distributed algorithms for community detection
• Gossip algorithms
• Graph partitioning via adaptive spectral techniques
• Locality in Distributed Graph Algorithms
• Lumpability and Commutativity of Markov Processes
• Networks, crowds and markets. Reasoning about a highly connected world.
• On the Analysis of a Label Propagation Algorithm for Community Detection
• Partitioning well-clustered graphs: spectral clustering works!
• Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
• Random graph coverings. I: General theory and graph connectivity
• Reaching a Consensus
• Reconstruction and estimation in the planted partition model
• Recovery and rigidity in a regular stochastic block model
• Social influence and opinions
• Spectral redemption in clustering sparse networks
• Step-By-Step Community Detection in Volume-Regular Graphs
• Sufficient Conditions for Convergence of the Sum–Product Algorithm
• Survey of local algorithms
• The Accuracy of the Gaussian Approximation to the Sum of Independent Variates
• The Metropolis algorithm for graph bisection
• The Rotation of Eigenvectors by a Perturbation. III
• The solution of some random NP-hard problems in polynomial expected time
• Timing in chemical reaction networks

Cited in

(7)

• Average whenever you meet: opportunistic protocols for community detection
• Distributed detection of clusters of arbitrary size
• Step-by-step community detection in volume-regular graphs
• A distributed community detection algorithm for large scale networks under stochastic block models
• Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
• Distributed community detection in dynamic graphs
• Find your place: simple distributed algorithms for community detection

Describes a project that uses

Uses Software

• Graft
• MathOverflow
• Giraph
• Pregel

This page was built for publication: Find Your Place: Simple Distributed Algorithms for Community Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115703)