PageRank and The K-Means Clustering Algorithm
This work addresses clustering and centrality analysis in graph-based and metric space data, but appears incremental as it extends existing algorithms to new settings.
The authors tackled the problem of generalizing the k-means clustering algorithm to graphs and other domains by using PageRank and centrality measures, resulting in a method that robustly computes node centrality and applies to directed/undirected graphs, point clouds, and triangulated meshes.
We utilize the PageRank vector to generalize the $k$-means clustering algorithm to directed and undirected graphs. We demonstrate that PageRank and other centrality measures can be used in our setting to robustly compute centrality of nodes in a given graph. Furthermore, we show how our method can be generalized to metric spaces and apply it to other domains such as point clouds and triangulated meshes