Community Detection in Scale-Free Networks: Approximation Algorithms for Maximizing Modularity
Authors:
- 17 May 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 31 (6) , 997-1006
Abstract
Many networks, indifferent of their function and scope, converge to a scale-free architecture in which the degree distribution approximately follows a power law. Meanwhile, many of those scale-free networks are found to be naturally divided into communities of densely connected nodes, known as community structure. Finding this community structure is a fundamental but challenging topic in network science. Since Newman's suggestion of using modularity as a measure to qualify the strength of community structure, many efficient methods that find community structure based on maximizing modularity have been proposed. However, there is a lack of approximation algorithms that provide provable quality bounds for the problem. In this paper, we propose polynomial-time approximation algorithms for the modularity maximization problem together with their theoretical justifications in the context of scale-free networks. We prove that the solutions of the proposed algorithms, even in the worst-case, are optimal up to a constant factor for scale-free networks with either bidirectional or unidirectional links. Even though our focus in this work is not on designing another empirically good algorithms to detect community structure, experiments on real-world networks suggest that the proposed algorithm is competitive with the state-of-the-art modularity maximization algorithm.Keywords
This publication has 36 references indexed in Scilit:
- Overlapping communities in dynamic networks2011
- Adaptive algorithms for detecting community structure in dynamic social networks2011
- An analysis of social network-based Sybil defensesACM SIGCOMM Computer Communication Review, 2010
- Multiresolution community detection for megascale networks by information-based replica correlationsPhysical Review E, 2009
- Constant-factor approximation algorithms for identifying dynamic communities2009
- Modularity clustering is force-directed layoutPhysical Review E, 2009
- Community Structure in Directed NetworksPhysical Review Letters, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences, 2008
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Competition and multiscaling in evolving networksEurophysics Letters, 2001