On the Complexity of Newman's Community Finding Approach for Biological and Social Networks
arXiv:1102.0969 · doi:10.1016/j.jcss.2012.04.003
Abstract
Given a graph of interactions, a module (also called a community or cluster) is a subset of nodes 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+\eps)-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 previously known NP-hardness results.
Journal of Computer and System Sciences, 2012
References in corpus (8)
- Modularity and community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Resolution limit in community detection
- Analysis of weighted networks
- Community structure in directed networks
- Classes of complex networks defined by role-to-role connectivity profiles
- Modularity-Maximizing Network Communities via Mathematical Programming
- Random graph models for directed acyclic networks
Cited by in corpus (8)
- Mixing local and global information for community detection in large networks
- Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
- DMCS : Density Modularity based Community Search
- Model-based clustering in networks with Stochastic Community Finding
- Additive Approximation Algorithms for Modularity Maximization
- Finding Influential Cores via Normalized Ricci Flows in Directed and Undirected Hypergraphs with Applications
- The parameterised complexity of computing the maximum modularity of a graph
- Modularity of regular and treelike graphs