Complex Network Analysis Techniques
Open access
Peer reviewed
Abstract
Abstract
ABSTRACT Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: Might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low‐degree polynomial framework) that testing between two options is as hard as finding the communities. Our methods give the first computational lower bounds for testing between two different “planted” distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. “null” distribution. We also show a formal relationship between the low‐degree frameworks for recovery in a planted model and for testing two planted models.
Direct answer
What can I do from this paper page?
Use this page to scan "Is It Easier to Count Communities Than Find Them?" quickly: start with the summary and abstract, then check the authors, source, topics, and related papers. From here, open Scollr to follow Complex Network Analysis Techniques research, save the paper, or map adjacent work.
Research areas
Follow related topics
Citation
BibTeX
@article{Rush2026Easier,
title = {Is It Easier to Count Communities Than Find Them?},
author = {Cynthia Rush and Fiona Skerman and Alexander S. Wein and Dana Yang},
journal = {Random Structures and Algorithms},
year = {2026},
doi = {10.1002/rsa.70071},
url = {https://doi.org/10.1002/rsa.70071}
}FAQ
Using this paper in a discovery workflow
How do I find related work for this paper?
Use the related papers and topic links on this page as starting points. In Scollr, you can also open the paper and build a literature map around its references, citing papers, and related work.
How can I keep up with new Complex Network Analysis Techniques research papers?
Follow Complex Network Analysis Techniques research in Scollr. New papers from the topic flow into a personalized feed, and you can save useful studies to revisit later.
Can I cite this paper from this page?
This page includes a static BibTeX block for Is It Easier to Count Communities Than Find Them?. Always verify the DOI, source, and publication details against the publisher record before submitting a manuscript.
Follow this research in Scollr
Follow the topics and authors behind this paper, save useful studies, and build a literature map when you are ready to go deeper.
Get the app