A Novel Method for Vertex Clustering in Dynamic Networks

In this paper, we introduce spatiotemporal graph \( k \) -means (STG \(k\) M), a novel, unsupervised method to cluster vertices within a dynamic network. Drawing inspiration from traditional \( k \) -means, STG \(k\) M 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.