Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
Authors:
- Thang N. DinhTDThang N. Dinh
- Xiang LiXLXiang Li
- My T. ThaiMTMy T. Thai
- 1 November 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 101-110
Abstract
Many social networks and complex systems are found to be naturally divided into clusters of densely connected nodes, known as community structure (CS). Finding CS is one of fundamental yet challenging topics in network science. One of the most popular classes of methods for this problem is to maximize Newman's modularity. However, there is a little understood on how well we can approximate the maximum modularity as well as the implications of finding community structure with provable guarantees. In this paper, we settle definitely the approximability of modularity clustering, proving that approximating the problem within any (multiplicative) positive factor is intractable, unless P = NP. Yet we propose the first additive approximation algorithm for modularity clustering with a constant factor. Moreover, we provide a rigorous proof that a CS with modularity arbitrary close to maximum modularity QOPT might bear no similarity to the optimal CS of maximum modularity. Thus even when CS with near-optimal modularity are found, other verification methods are needed to confirm the significance of the structure.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Community Detection in Scale-Free Networks: Approximation Algorithms for Maximizing ModularityIEEE Journal on Selected Areas in Communications, 2013
- An adaptive approximation algorithm for community detection in dynamic scale-free networks2013
- On the complexity of Newmanʼs community finding approach for biological and social networksJournal of Computer and System Sciences, 2013
- Community detection algorithms: A comparative analysisPhysical Review E, 2009
- Computational Complexity2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Sparsest cuts and bottlenecks in graphsDiscrete Applied Mathematics, 1990
- How well can a graph be n-colored?Discrete Mathematics, 1981