An adaptive approximation algorithm for community detection in dynamic scale-free networks
Authors:
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 55-59
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Finding Statistically Significant Communities in NetworksPLOS ONE, 2011
- Adaptive algorithms for detecting community structure in dynamic social networks2011
- BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant NetworksIEEE Transactions on Mobile Computing, 2010
- Community detection algorithms: A comparative analysisPhysical Review E, 2009
- On the evolution of user interaction in Facebook2009
- SybilGuard: Defending Against Sybil Attacks via Social NetworksIEEE/ACM Transactions on Networking, 2008
- Facetnet2008
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Evolution of the social network of scientific collaborationsPhysica A: Statistical Mechanics and its Applications, 2002
- Scale-free characteristics of random networks: the topology of the world-wide webPhysica A: Statistical Mechanics and its Applications, 2000