科研之友
微信
新浪微博
Facebook
分享链接
摘要
We introduce ACS, an adaptive framework with approximation guarantees for quickly identifying community structure in dynamic networks via maximizing Modularity Q. Our framework explores the advantages of the power-law distribution property found in many real-world complex systems. The framework 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 scale-free 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 ACS in a wide range of dynamic networks.
- 出版日期2015-10
