Exact and rapid linear clustering of networks with dynamic programming

Alice Patania, Antoine Allard, Jean-Gabriel Young
1/25/2023
cs.SIcs.DScs.LG

No official code found. Best implementation: jg-you/dyvider (16 stars, MIT, last commit 2023-07-04).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

jg-you/dyviderCommunity100%
MIT

Dynamic programming algorithms for exact linear clustering in networks.

163Python, Jupyter NotebookJan 14, 20233 years agoMIT
clusteringgraph-algorithmsmachine-learningnetwork-embedding

Similar Papers

FOSC-X: An Extended Framework for Optimal Local Cuts and Non-Horizontal Cluster Selection from Clustering Hierarchies

84% match2026

Dynamic Spectral Clustering with Provable Approximation Guarantee

83% match1 repo32024

Large Scale Constrained Clustering With Reinforcement Learning

81% match2024

Spectral Clustering with Graph Neural Networks for Graph Pooling

80% match2 repos2782019

Neural network-based clustering using pairwise constraints

80% match1 repo712015

Ultrametric Cluster Hierarchies: I Want 'em All!

80% match2025

Cite this paper

@article{patania2023exact,
  title  = {Exact and rapid linear clustering of networks with dynamic programming},
  author = {Alice Patania and Antoine Allard and Jean-Gabriel Young},
  year   = {2023},
  eprint = {2301.10403},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2301.10403v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2301.10403.svg)](https://codeofpaper.com/paper/2301.10403)

Discussion