On the Complexity of Newman's Community Finding Approach for Biological and Social Networks
Preprint
Abstract
Given a graph of interactions, a module (also called a community or cluster) is a subset of vertices whose fitness is a function of the statistical significance of the pairwise interactions of nodes in the module. The topic of this paper is a model-based community finding approach, commonly referred to as modularity clustering, that was originally proposed by Newman and has subsequently been extremely popular in practice. Various heuristic methods are currently employed for finding the optimal solution. However, the exact computational complexity of this approach is still largely unknown. To this end, we initiate a systematic study of the computational complexity of modularity clustering. Due to the specific quadratic nature of the modularity function, it is necessary to study its value on sparse graphs and dense graphs separately. Our main results include a (1+\epsilon)-inapproximability for dense graphs and a logarithmic approximation for sparse graphs. We make use of several combinatorial properties of modularity to get these results. These are the first non-trivial approximability results beyond the NP-hardness results.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Random graph models for directed acyclic networksPhysical Review E, 2009
- Tight Lower Bounds on the Size of a Maximum Matching in a Regular GraphGraphs and Combinatorics, 2007
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Classes of complex networks defined by role-to-role connectivity profilesNature Physics, 2006
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Complexity of approximating bounded variants of optimization problemsTheoretical Computer Science, 2005
- Maximizing Quadratic Programs: Extending Grothendieck's Inequality2004
- Analysis of weighted networksPhysical Review E, 2004
- Finding and evaluating community structure in networksPhysical Review E, 2004
- The regularity lemma and approximation schemes for dense problems2002