Algorithm independent bounds on community detection problems and associated transitions in stochastic block model graphs

DOI10.1093/comnet/cnu042zbMath1397.05172arXiv1306.5794OpenAlexW2963285371MaRDI QIDQ4689361

David R. Reichman, Peter Ronhovde, Richard K. Darst, Zohar Nussinov

Publication date: 16 October 2018

Published in: Journal of Complex Networks (Search for Journal in Brave)

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

zbMATH Keywords

clustering solvability community detection stochastic block model NP hard edgedensity

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Algorithm independent bounds on community detection problems and associated transitions in stochastic block model graphs