Exact and rapid linear clustering of networks with dynamic programming
This solves the problem of exact linear clustering for researchers and practitioners in network analysis, offering a more accurate alternative to approximate methods.
The authors tackled the problem of clustering networks with nodes in a single dimension, such as prestige hierarchies or hyperbolic embeddings, by introducing a dynamic programming approach that provides provably optimal solutions in O(n^2) time, outperforming existing heuristics significantly.
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.