# Dissecting graph measure performance for node clustering in LFR parameter space

arXiv: https://arxiv.org/abs/2202.09827 · HTML: https://mlsanity.com/paper/2202.09827/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 60 references that are in the map.
- First posted on arXiv 20 Feb 2022.

## Builds on (most cited first, 7 of 7)

- [Using synthetic networks for parameter tuning in community detection](https://mlsanity.com/paper/1906.04555/) (2019)
- [Randomized Optimal Transport on a Graph: framework and new distance measures](https://mlsanity.com/paper/1806.03232/) (2018)
- [Accounting for the Role of Long Walks on Networks via a New Matrix Function](https://mlsanity.com/paper/1607.06807/) (2016)
- [Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism](https://mlsanity.com/paper/1902.03002/) (2019)
- [Randomized Shortest Paths with Net Flows and Capacity Constraints](https://mlsanity.com/paper/1910.01849/) (2019)
- [Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization](https://mlsanity.com/paper/2007.00419/) (2020)
- [Impact of network topology on efficiency of proximity measures for community detection](https://mlsanity.com/paper/2111.01229/) (2021)

## Abstract (arXiv)

Graph measures that express closeness or distance between nodes can be employed for graph nodes clustering using metric clustering algorithms. There are numerous measures applicable to this task, and which one performs better is an open question. We study the performance of 25 graph measures on generated graphs with different parameters. While usually measure comparisons are limited to general measure ranking on a particular dataset, we aim to explore the performance of various measures depending on graph features. Using an LFR graph generator, we create a dataset of 11780 graphs covering the whole LFR parameter space. For each graph, we assess the quality of clustering with k-means algorithm for each considered measure. Based on this, we determine the best measure for each area of the parameter space. We find that the parameter space consists of distinct zones where one particular measure is the best. We analyze the geometry of the resulting zones and describe it with simple criteria. Given particular graph parameters, this allows us to recommend a particular measure to use for clustering.