Exact and rapid linear clustering of networks with dynamic programming
arXiv:2301.10403 · doi:10.1098/rspa.2023.0159
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.
arXiv comment14 pages, 8 figures
References in corpus (22)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Spatial Networks
- Stochastic blockmodels and community structure in networks
- An Algorithm for Optimal Partitioning of Data on an Interval
- Network Geometry
- Evaluating Overfit and Underfit in Models of Network Community Structure
- Friendship networks and social status
- Aspirational pursuit of mates in online dating markets
- Improved mutual information measure for classification and community detection
- The impossibility of low rank representations for triangle-rich complex networks
- Community detection in networks using graph embeddings
- Detecting the ultra low dimensionality of real networks
- Universality of the stochastic block model
- First-principles multiway spectral partitioning of graphs
- Ranking with multiple types of pairwise comparisons
- Belief propagation for permutations, rankings, and partial orders
- Consistency between ordering and clustering methods for graphs
- Finding community structure using the ordered random graph model