Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427348 | Information Processing Letters | 2014 | 4 Pages |
Abstract
•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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bhaskar DasGupta, Devendra Desai,