The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

zbMath1409.68220arXiv1702.00467MaRDI QIDQ4967226

Moore, Cristopher

Publication date: 3 July 2019

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

Mathematics Subject Classification ID

Bayesian inference (62F15) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (27)

Optimal group testing ⋮ Estimation of low-rank matrices via approximate message passing ⋮ Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks ⋮ The algorithmic hardness threshold for continuous random energy models ⋮ Aligning random graphs with a sub-tree similarity message-passing algorithm ⋮ Core-Periphery Structure in Networks (Revisited) ⋮ Detection thresholds in very sparse matrix completion ⋮ The planted matching problem: sharp threshold and infinite-order phase transition ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Charting the replica symmetric phase ⋮ Charting the replica symmetric phase ⋮ Community Detection and Stochastic Block Models ⋮ Spin systems on Bethe lattices ⋮ Unnamed Item ⋮ Convex relaxation methods for community detection ⋮ Unnamed Item ⋮ The overlap gap property in principal submatrix recovery ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Group synchronization on grids ⋮ Partial recovery bounds for clustering with the relaxed \(K\)-means ⋮ The planted matching problem: phase transitions and exact results ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Testing degree corrections in stochastic block models ⋮ Mean-field theory of graph neural networks in graph partitioning ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ Relating Modularity Maximization and Stochastic Block Models in Multilayer Networks

This page was built for publication: The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness