Hierarchical Graph Clustering using Node Pair Sampling
This work addresses graph clustering for revealing multi-scale structures, but it appears incremental as it builds on modularity-based techniques with a novel distance measure.
The paper tackles the problem of hierarchical graph clustering by introducing an agglomerative algorithm based on node pair sampling distances, proving reducibility to enable efficient nearest-neighbor chain agglomeration, and demonstrating results on synthetic and real datasets.
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.