Fast Hierarchical Graph Clustering in Linear-Time

Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, Sungchul Kim

Abstract

While there has been a lot of research on graph clustering (community detection), most work (i) does not address the hierarchical community detection problem or are (ii) inefficient for large networks. In this work, we describe an approach called hLP that addresses both these limitations. Notably, hLP is fast and efficient for discovering a hierarchy of communities in large networks with a worst-case time and space complexity that is linear in the number of edges and nodes, respectively. The experiments demonstrate the effectiveness of hLP. Finally, we show an application for visualizing large networks with hundreds of thousands of nodes and edges.
BibTeX
@inproceedings{rossi2020fast,
  author = {Ryan A. Rossi and Nesreen K. Ahmed and Eunyee Koh and Sungchul Kim},
  title = {{Fast Hierarchical Graph Clustering in Linear-Time}},
  booktitle = {The Web Conference},
  year = {2020},
  doi = {10.1145/3366424.3382673},
}
Figure