A Novel Method for Vertex Clustering in Dynamic Networks

In this paper, we introduce spatiotemporal graph k-means (STGkM), a novel, unsupervised method to cluster vertices within a dynamic network. Drawing inspiration from traditional k-means, STGkM finds both short-term dynamic clusters and a "long-lived" partitioning of vertices within a network whose topology is evolving over time. We provide an exposition of the algorithm, illuminate its operation on synthetic data, and apply it to detect political parties from a dynamic network of voting data in the United States House of Representatives. One of the main advantages of STGkM is that it has only one required parameter, namely k; we therefore include an analysis of the range of this parameter and guidance on selecting its optimal value. We also give certain theoretical guarantees about the correctness of our algorithm.