An adaptive approximation algorithm for community detection in dynamic scale-free networks

We introduce A3CS, an adaptive framework with approximation guarantees for quickly identifying community structure in dynamic networks via maximizing Modularity Q. Our framework explores the advantages of power-law distribution property, is scalable for very large networks, and more excitingly, possesses approximation factors to ensure the quality of its detected community structure. To the best of our knowledge, this is the first framework that achieves approximation guarantees for the NP-hard modularity maximization problem, especially on dynamic networks. To certify our approach, we conduct extensive experiments in comparison with other adaptive methods on both synthesized networks with known community structures and real-world traces including ArXiv e-print citation and Facebook social networks. Excellent empirical results not only confirm our theoretical results but also promise the practical applicability of A3CS in a wide range of dynamic networks.