EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Is It Easier to Count Communities Than Find Them?

Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang

Random Structures & Algorithms · 2026-07 · 68 (4)

DOI: 10.1002/rsa.70071 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 09.06.2026. Verfasst von Cynthia Rush und 3 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Knut och Alice Wallenbergs Stiftelse, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Knut och Alice Wallenbergs Stiftelse
  • National Science Foundation

Zitieren

APA

Rush, C., Skerman, F., Wein, A. S., & Yang, D. (2026). Is It Easier to Count Communities Than Find Them?. Random Structures & Algorithms, 68(4). https://doi.org/10.1002/rsa.70071

Vancouver

Rush C, Skerman F, Wein AS, Yang D. Is It Easier to Count Communities Than Find Them?. Random Structures & Algorithms. 2026;68(4). doi:10.1002/rsa.70071

BibTeX
@article{Rush2026,
  author = {Rush, Cynthia and Skerman, Fiona and Wein, Alexander S. and Yang, Dana},
  title = {Is It Easier to Count Communities Than Find Them?},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {4},
  doi = {10.1002/rsa.70071}
}
Kostenlos starten →