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=\left(V,E\right)$, a subset $S\subseteq V$ is an $\left(\alpha ,\beta \right)$-community if: * Every member of the community is friends with an $\alpha$-fraction of the community; * Every non-member is friends with at most a $\beta$-fraction of the community. Arora et al [AGSS12] gave a quasi-polynomial time algorithm for enumerating all the $\left(\alpha ,\beta \right)$-communities for any constants $\alpha >\beta$. 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,o\left(1\right)\right)$-community; and * $G$ does not contain an $\left(\beta +o\left(1\right),\beta \right)$-community for any $\beta \in \left[0,1\right]$. We also prove that counting the number of $\left(1,o\left(1\right)\right)$-communities requires quasi-polynomial time assuming the weaker #ETH.

References in corpus (6)

• Community detection in graphs
• Axioms for graph clustering quality functions
• Community Recovery in Graphs with Locality
• Mixture Selection, Mechanism Design, and Signaling
• Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach
• Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Cited by in corpus (2)

• ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
• Inapproximability of VC Dimension and Littlestone's Dimension