Hierarchical Graph Clustering using Node Pair Sampling

Thomas Bonald, Bertrand Charpentier, Alexis Galland, Alexandre Hollocou
6/5/2018
cs.SIcs.AI

Official code: tbonald/paris (38 stars, last commit 2018-06-22). 1 more implementation below.

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.

View on arXivView PDF

Code Implementations(2)

tbonald/parisOfficial100%

Hierarchical graph clustering

387Python, Jupyter NotebookFeb 12, 20188 years ago
clusteringdendrogramgraphhierarchynetworkx
sharpenb/Hierarchical-Paris-ClusteringOfficial100%

Hierarchical Graph Clustering using Node Pair Sampling (MLG, KDD Workshop) - Multi-scale Clustering in Graphs using Modularity (DiVA)

173Python, MakefileApr 16, 20186 years ago

Similar Papers

ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain

89% match1 repo82021

Ensemble Clustering for Graphs

85% match1 repo302018

A Clustering Method with Graph Maximum Decoding Information

84% match2024

Spectral Clustering with Graph Neural Networks for Graph Pooling

83% match2 repos2782019

Ensemble Clustering for Graphs: Comparisons and Applications

83% match1 repo302019

Learning Hierarchical Graph Neural Networks for Image Clustering

83% match1 repo14.3k2021

Cite this paper

@article{bonald2018hierarchical,
  title  = {Hierarchical Graph Clustering using Node Pair Sampling},
  author = {Thomas Bonald and Bertrand Charpentier and Alexis Galland and Alexandre Hollocou},
  year   = {2018},
  eprint = {1806.01664},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1806.01664}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1806.01664.svg)](https://codeofpaper.com/paper/1806.01664)

Discussion