Hierarchical Graph Clustering using Node Pair Sampling
arXiv:1806.01664
Abstract
We present a novel hierarchical graph clustering algorithm inspired by modularity-based clustering techniques. The algorithm is agglomerative and based on a simple distance between clusters induced by the probability of sampling node pairs. We prove that this distance is reducible, which enables the use of the nearest-neighbor chain to speed up the agglomeration. The output of the algorithm is a regular dendrogram, which reveals the multi-scale structure of the graph. The results are illustrated on both synthetic and real datasets.
References in corpus (13)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Fast algorithm for detecting community structure in networks
- Resolution limit in community detection
- Hierarchical structure and the prediction of missing links in networks
- Statistical Mechanics of Community Detection
- Detecting the overlapping and hierarchical community structure of complex networks
- Extracting the hierarchical organization of complex systems
- Limits of modularity maximization in community detection
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Multiresolution community detection for megascale networks by information-based replica correlations
Cited by in corpus (5)
- Shock-induced melting and crystallization in titanium irradiated by ultrashort laser pulse
- Multiscale mobility patterns and the restriction of human movement
- On Comparing and Enhancing Common Approaches to Network Community Detection
- Comparison and Benchmark of Graph Clustering Algorithms
- Learning Hierarchical Graph Neural Networks for Image Clustering