# Exact and rapid linear clustering of networks with dynamic programming

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 60 references that are in the map.
- First posted on arXiv 25 Jan 2023.

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

- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Understanding graph embedding methods and their applications](https://mlsanity.com/paper/2012.08019/) (2020)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Network Geometry](https://mlsanity.com/paper/2001.03241/) (2020)
- [Evaluating Overfit and Underfit in Models of Network Community Structure](https://mlsanity.com/paper/1802.10582/) (2018)
- [Community detection in networks using graph embeddings](https://mlsanity.com/paper/2009.05265/) (2020)
- [Pairwise Choice Markov Chains](https://mlsanity.com/paper/1603.02740/) (2016)
- [A physical model for efficient ranking in networks](https://mlsanity.com/paper/1709.09002/) (2017)
- [Mercator: uncovering faithful hyperbolic embeddings of complex networks](https://mlsanity.com/paper/1904.10814/) (2019)
- [Improved mutual information measure for classification and community detection](https://mlsanity.com/paper/1907.12581/) (2019)
- [Universality of the stochastic block model](https://mlsanity.com/paper/1806.04214/) (2018)
- [Aspirational pursuit of mates in online dating markets](https://mlsanity.com/paper/1808.04840/) (2018)
- [Detecting the ultra low dimensionality of real networks](https://mlsanity.com/paper/2110.14507/) (2021)
- [Ranking with multiple types of pairwise comparisons](https://mlsanity.com/paper/2206.13580/) (2022)
- [Belief propagation for permutations, rankings, and partial orders](https://mlsanity.com/paper/2110.00513/) (2021)
- [Community Detection in the Hyperbolic Space](https://mlsanity.com/paper/1906.09082/) (2019)
- [Clustering implies geometry in networks](https://mlsanity.com/paper/1604.01575/) (2016)
- [Comment on "Improved mutual information measure for clustering, classification, and community detection"](https://mlsanity.com/paper/2005.07007/) (2020)
- [Embedding-aided network dismantling](https://mlsanity.com/paper/2208.01087/) (2022)
- [Consistency between ordering and clustering methods for graphs](https://mlsanity.com/paper/2208.12933/) (2022)
- [Linear Clustering Process on Networks](https://mlsanity.com/paper/2209.11617/) (2022)
- [Local dominance unveils clusters in networks](https://mlsanity.com/paper/2209.15497/) (2022)
- [Finding community structure using the ordered random graph model](https://mlsanity.com/paper/2210.08989/) (2022)

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

- [Zoo Guide to Network Embedding](https://mlsanity.com/paper/2305.03474/) (2023)
- [Symmetry-driven embedding of networks in hyperbolic space](https://mlsanity.com/paper/2406.10711/) (2024)

## Abstract (arXiv)

We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, for example prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions to this problem. Here, we introduce a dynamic programming approach that returns provably optimal solutions in polynomial time -- O(n^2) steps -- for a broad class of clustering objectives. We demonstrate the algorithm through applications to synthetic and empirical networks and show that it outperforms existing heuristics by a significant margin, with a similar execution time.