Step-by-step community detection in volume-regular graphs

DOI10.1016/j.tcs.2020.09.036zbMath1467.68133arXiv1907.07149OpenAlexW2990342737MaRDI QIDQ2210514

Emilio Cruciani, Francesco Pasquale, Sara Rizzo, Luca Becchetti

Publication date: 6 November 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainsspectral analysisdistributed algorithmscommunity detection

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distributed algorithms (68W15) Random walks on graphs (05C81)

Related Items (3)

Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ Biased opinion dynamics: when the devil is in the details ⋮ Distributed detection of clusters of arbitrary size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Belief propagation, robust reconstruction and optimal recovery of block models
• A simple population protocol for fast robust approximate majority
• The Metropolis algorithm for graph bisection
• A proof of the block model threshold conjecture
• Distributed probabilistic polling and applications to proportionate agreement
• Spectral redemption in clustering sparse networks
• Exact Recovery in the Stochastic Block Model
• The solution of some random NP-hard problems in polynomial expected time
• Sufficient Conditions for Convergence of the Sum–Product Algorithm
• Graph Partitioning via Adaptive Spectral Techniques
• Community Detection and Stochastic Block Models
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Eigenvector Computation and Community Detection in Asynchronous Gossip Models
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Lumpability and Commutativity of Markov Processes
• On the Analysis of a Label Propagation Algorithm for Community Detection
• Partitioning Well-Clustered Graphs: Spectral Clustering Works!
• The Accuracy of the Gaussian Approximation to the Sum of Independent Variates
• On a lemma of Littlewood and Offord
• Step-By-Step Community Detection in Volume-Regular Graphs
• Concentration of Measure for the Analysis of Randomized Algorithms
• A decentralized algorithm for spectral analysis

This page was built for publication: Step-by-step community detection in volume-regular graphs