mlsanityData to 7 Oct 2026

Exact and rapid linear clustering of networks with dynamic programming

arXiv 2301.10403 ↗First posted 25 Jan 2023cs.SI cs.DS cs.LGcited by 2

Not on the map. Why?

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.

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

Builds on

24 of 60 references.

References · 24

  1. 2019Hyperbolic Graph Convolutional Neural Networkscited by 400
  2. 2014PageRank beyond the Webcited by 51
  3. 2020Understanding graph embedding methods and their applicationscited by 50
  4. 2020The impossibility of low rank representations for triangle-rich complex networkscited by 32
  5. 2020Network Geometrycited by 31
  6. 2018Evaluating Overfit and Underfit in Models of Network Community Structurecited by 17
  7. 2020Community detection in networks using graph embeddingscited by 11
  8. 2017A physical model for efficient ranking in networkscited by 10
  9. 2019Mercator: uncovering faithful hyperbolic embeddings of complex networkscited by 10
  10. 2016Pairwise Choice Markov Chainscited by 8
  11. 2019Improved mutual information measure for classification and community detectioncited by 6
  12. 2018Universality of the stochastic block modelcited by 5
12 more
  1. 2018Aspirational pursuit of mates in online dating marketscited by 5
  2. 2021Detecting the ultra low dimensionality of real networkscited by 5
  3. 2021Belief propagation for permutations, rankings, and partial orderscited by 4
  4. 2022Ranking with multiple types of pairwise comparisonscited by 4
  5. 2019Community Detection in the Hyperbolic Spacecited by 3
  6. 2016Clustering implies geometry in networkscited by 2
  7. 2020Comment on "Improved mutual information measure for clustering, classification, and community detection"cited by 2
  8. 2022Embedding-aided network dismantlingcited by 2
  9. 2022Consistency between ordering and clustering methods for graphscited by 1
  10. 2022Linear Clustering Process on Networkscited by 1
  11. 2022Local dominance unveils clusters in networkscited by 1
  12. 2022Finding community structure using the ordered random graph modelcited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1.

2 papers.

  1. 2023Zoo Guide to Network Embeddingcited by 2
  2. 2024Symmetry-driven embedding of networks in hyperbolic spacecited by 1