Exact and rapid linear clustering of networks with dynamic programming
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.
Code (1)
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs
Recent advances in symbolic dynamic programming (SDP) combined with the extended algebraic decision diagram (XADD) data structure have provided exact solutions for mixed discrete and continuous (hybrid) MDPs with piecewi…
Exact and Heuristic Algorithms for Constrained Biclustering
Biclustering, also known as co-clustering or two-way clustering, simultaneously partitions the rows and columns of a data matrix to reveal submatrices with coherent patterns. Incorporating background knowledge into clust…
Data Structures & Algorithms for Exact Inference in Hierarchical Clustering
Hierarchical clustering is a fundamental task often used to discover meaningful structures in data, such as phylogenetic trees, taxonomies of concepts, subtypes of cancer, and cascades of particle decays in particle phys…
ClusteringSmall Data Image ClassificationFast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
The $k$-Means clustering problem on $n$ points is NP-Hard for any dimension $d\ge 2$, however, for the 1D case there exists exact polynomial time algorithms. Previous literature reported an $O(kn^2)$ time dynamic program…
ClusteringFast nonlinear risk assessment for autonomous vehicles using learned conditional probabilistic models of agent futures
This paper presents fast non-sampling based methods to assess the risk for trajectories of autonomous vehicles when probabilistic predictions of other agents' futures are generated by deep neural networks (DNNs). The pre…
Autonomous VehiclesPosition