1Community Detection in Scale-free Networks: Approximation Algorithms for Maximizing Modularity

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 efficien methods that fin 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 justification 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. Index Terms—Network science, approximation algorithm, community structure, modularity, social networks