# Detecting communities is hard, and counting them is even harder

arXiv: https://arxiv.org/abs/1611.08326 · HTML: https://mlsanity.com/paper/1611.08326/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [A Note on Hardness of Computing Recursive Teaching Dimension](https://mlsanity.com/paper/2307.09792/) (2023)

## Abstract (arXiv)

We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph G=left(V,Eright), a subset Ssubseteq V is an left(α,βright)-community if: * Every member of the community is friends with an α-fraction of the community; * Every non-member is friends with at most a β-fraction of the community. Arora et al [AGSS12] gave a quasi-polynomial time algorithm for enumerating all the left(α,βright)-communities for any constants α>β. Here, we prove that, assuming the Exponential Time Hypothesis (ETH), quasi-polynomial time is in fact necessary - and even for a much weaker approximation desideratum. Namely, distinguishing between: * G contains an left(1,oleft(1right)right)-community; and * G does not contain an left(β+oleft(1right),βright)-community for any β∈left[0,1right]. We also prove that counting the number of left(1,oleft(1right)right)-communities requires quasi-polynomial time assuming the weaker #ETH.