On a connection between small set expansions and modularity clustering

• We relate the small-set expansion problem to the modularity clustering problem.
• We consider a sub-exponential time algorithm for small-set expansion problem.
• We show that it leads to a sub-exponential approximation for modularity clustering.

In this paper we explore a connection between two seemingly different problems from two different domains: the small-set expansion problem studied in unique games conjecture, and a popular community finding approach for social networks known as the modularity clustering approach. We show that a sub-exponential time algorithm for the small-set expansion problem leads to a sub-exponential time constant factor approximation for some hard input instances of the modularity clustering problem.