Hierarchical Graph Clustering using Node Pair Sampling

Thomas Bonald (1, 2) , Bertrand Charpentier (1, 2) , Alexis Galland (3) , Alexandre Hollocou (3, 2)

1 Télécom ParisTech
2 LINCS - Laboratory of Information, Network and Communication Sciences
3 DYOGENE - Dynamics of Geometric Networks

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.

Domaines: Apprentissage [cs.LG]; Algorithme et structure de données [cs.DS]

Thomas Bonald, Bertrand Charpentier, Alexis Galland, Alexandre Hollocou. Hierarchical Graph Clustering using Node Pair Sampling. MLG 2018 - 14th International Workshop on Mining and Learning with Graphs, Aug 2018, London, United Kingdom. ⟨hal-01887669⟩