Computational complexity, phase transitions, and message-passing for community detection
DOI10.1093/ACPROF:OSO/9780198743736.003.0002zbMATH Open1344.68098OpenAlexW1791226750MaRDI QIDQ2990197FDOQ2990197
Authors: Cristopher Moore 
Publication date: 29 July 2016
Published in: Statistical Physics, Optimization, Inference, and Message-Passing Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1093/acprof:oso/9780198743736.003.0002
Recommendations
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- Information, Physics, and Computation
- Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
- Algorithm independent bounds on community detection problems and associated transitions in stochastic block model graphs
- Phase Transitions in Combinatorial Optimization Problems
computational complexitycommunity detectionnetworkscomplexity classesphase transitionshardnessrandom graphsbelief propagationrandom \(k\)-SAT
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial probability (60C05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Phase transitions (general) in equilibrium statistical mechanics (82B26)
Cited In (3)
This page was built for publication: Computational complexity, phase transitions, and message-passing for community detection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2990197)
