Computational complexity, phase transitions, and message-passing for community detection

DOI10.1093/ACPROF:OSO/9780198743736.003.0002MaRDI QIDQ2990197zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexitycommunity detectionnetworkscomplexity classesphase transitionshardnessrandom graphsbelief propagationrandom \(k\)-SAT

Mathematics Subject Classification ID

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)

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

Cited in

(4)

• Disordered systems insights on computational hardness
• Computing exact \(p\)-values for community detection
• Phase Transitions in Spectral Community Detection
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

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)