Fast Algorithm for Modularity-Based Graph Clustering
Abstract
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.
Cite
Text
Shiokawa et al. "Fast Algorithm for Modularity-Based Graph Clustering." AAAI Conference on Artificial Intelligence, 2013. doi:10.1609/AAAI.V27I1.8455Markdown
[Shiokawa et al. "Fast Algorithm for Modularity-Based Graph Clustering." AAAI Conference on Artificial Intelligence, 2013.](https://mlanthology.org/aaai/2013/shiokawa2013aaai-fast/) doi:10.1609/AAAI.V27I1.8455BibTeX
@inproceedings{shiokawa2013aaai-fast,
title = {{Fast Algorithm for Modularity-Based Graph Clustering}},
author = {Shiokawa, Hiroaki and Fujiwara, Yasuhiro and Onizuka, Makoto},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2013},
pages = {1170-1176},
doi = {10.1609/AAAI.V27I1.8455},
url = {https://mlanthology.org/aaai/2013/shiokawa2013aaai-fast/}
}