# Consistency between ordering and clustering methods for graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 60 references that are in the map.
- First posted on arXiv 27 Aug 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Bayesian stochastic blockmodeling](https://mlsanity.com/paper/1705.10225/) (2017)
- [Impact of regularization on Spectral Clustering](https://mlsanity.com/paper/1312.1733/) (2013)
- [Spectral Clustering of Graphs with the Bethe Hessian](https://mlsanity.com/paper/1406.1880/) (2014)
- [A Comparative Analysis of Community Detection Algorithms on Artificial Networks](https://mlsanity.com/paper/1608.00763/) (2016)
- [Understanding Regularized Spectral Clustering via Graph Conductance](https://mlsanity.com/paper/1806.01468/) (2018)
- [Improving the performance of algorithms to find communities in networks](https://mlsanity.com/paper/1311.3984/) (2013)
- [Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors](https://mlsanity.com/paper/1502.06775/) (2015)
- [Detectability of the spectral method for sparse graph partitioning](https://mlsanity.com/paper/1509.06484/) (2015)
- [Sequential locality of graphs and its hypothesis testing](https://mlsanity.com/paper/2111.11267/) (2021)

## Built on by (most cited first, 1 of 1)

- [Exact and rapid linear clustering of networks with dynamic programming](https://mlsanity.com/paper/2301.10403/) (2023)

## Abstract (arXiv)

A relational dataset is often analyzed by optimally assigning a label to each element through clustering or ordering. While similar characterizations of a dataset would be achieved by both clustering and ordering methods, the former has been studied much more actively than the latter, particularly for the data represented as graphs. This study fills this gap by investigating methodological relationships between several clustering and ordering methods, focusing on spectral techniques. Furthermore, we evaluate the resulting performance of the clustering and ordering methods. To this end, we propose a measure called the label continuity error, which generically quantifies the degree of consistency between a sequence and partition for a set of elements. Based on synthetic and real-world datasets, we evaluate the extents to which an ordering method identifies a module structure and a clustering method identifies a banded structure.