Detecting communities is Hard (And Counting Them is Even Harder)

Abstract

We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph G, a subset
S of vertices is an (a,b)-community if: * Every member of the community is friends with an (a)-fraction of the community; and
* every non-member is friends with at most a (b)-fraction of the
community. 

[Arora, Ge, Sachdeva, Schoenebeck 2012] gave a quasi-polynomial
time algorithm for enumerating all the (a,b)-communities
for any constants a>b. 

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 (1,o(1))-community; and
* G does not contain a (b,b+o(1))-community
for any b.

We also prove that counting the number of (1,o(1))-communities
requires quasi-polynomial time assuming the weaker #ETH.