AAAI Publications, Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Fast Algorithm for Modularity-Based Graph Clustering
Hiroaki Shiokawa, Yasuhiro Fujiwara, Makoto Onizuka

Last modified: 2013-06-29


In AI and Web communities, modularity-based graph clustering algorithms are being applied to various applications. However, existing algorithms are not applied to large graphs because they have to scan all vertices/edges iteratively. The goal of this paper is to efficiently compute clusters with high modularity from extremely large graphs with more than a few billion edges. The heart of our solution is to compute clusters by incrementally pruning unnecessary vertices/edges and optimizing the order of vertex selections. Our experiments show that our proposal outperforms all other modularity-based algorithms in terms of computation time, and it finds clusters with high modularity.


Graph; Clustering; Modularity

Full Text: PDF