A near-optimal adaptive algorithm for maximizing modularity in dynamic scale-free networks

Thang N. Dinh (), Nam P. Nguyen (), Md Abdul Alim () and My T. Thai ()
Additional contact information
Thang N. Dinh: University of Florida
Nam P. Nguyen: University of Florida
Md Abdul Alim: University of Florida
My T. Thai: University of Florida

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 21, 747-767

Abstract: Abstract We introduce A $$^3$$ 3 CS, 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 A $$^3$$ 3 CS in a wide range of dynamic networks.

Keywords: Adaptive approximation algorithm; Community structure; Modularity; Social networks (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9665-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9665-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9665-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().