  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.
