BH-tsNET, FIt-tsNET, and L-tsNET: Fast tsNET Algorithms for Large Graph Drawing.

A simple and practical $o(\sqrt{n})$-time algorithm for shortest paths in power law graphs

PBS is proposed and analyzed, a simple sublinear approximation algorithm for power-law graphs with parameter $\beta\in[2,3)$ that does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size).

The K-SCAN Clustering Algorithm

In the Big Data era, the scalability of clustering algorithms constitutes a key challenge. Traditional density-based methods (e.g., DBSCAN) offer robustness to noise and the ability to detect non-linear clusters, yet their quadratic time complexity $O(N^2)$ drastically limits their applicability. Conversely, partitional algorithms (e.g., K-Means), with their linear complexity $O(N)$, impose sphericity on the resulting groups and fail in the presence of outliers. This paper presents K-SCAN -- a novel hybrid algorithm that optimizes this trade-off. The method integrates preliminary vector quantization (stochastic Mini-Batch K-Means) to extract a reduced set of weighted micro-clusters, followed by a subsequent density-based structural analysis. Empirical evaluation on datasets of up to $10^6$ samples confirms the linear computational complexity of the proposed solution. K-SCAN achieves more than a 3-fold speed-up over the hierarchical BIRCH algorithm, avoiding the costly management of tree-based structures. The method precisely identifies non-linear manifolds while maintaining structural stability (Adjusted Rand Index>0.99), even with noise levels reaching 55\% of the data volume. The main limitation of the proposed algorithm, which could not be fully eliminated in the present study, remains its susceptibility to over-smoothing and its difficulty in separating clusters with highly heterogeneous local density. In complex visual spaces, this can lead to the loss of the finest topological details.

Incremental ( 𝒌, 𝒛 ) -Clustering on Graphs

Average Distance Approximation for Static Large Graphs

The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.

Towards Tight Robust Coresets for k-Medians Clustering

The techniques introduce novel dataset decompositions, enabling chaining arguments to be applied jointly across multiple components to solve the robust k -medians problem with m outliers.

Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise

Lloyd's $K$-means algorithm, also known as na\"{i}ve $K$-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all $K$-partitions of a dataset via iterative cluster refinement. In this work, we establish a novel connection between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a prominent first-order method for projection-free optimization. We demonstrate that Lloyd's algorithm is a special case of FW. Leveraging recent advances in FW methods for concave objectives, we derive a non-asymptotic $\mathcal{O}(1/t)$ convergence rate to a local minimum of the SSE objective. To account for empty clusters, an outcome possible under Lloyd's greedy assignment, we develop an FW variant for semismooth objectives while retaining the same convergence rate that is solely controlled by the initial SSE value. We illustrate our findings with a simulation study for spherical Gaussian mixtures and a real-world image segmentation dataset.