Soft Partition Markov Stability for Graph Clustering

We propose soft partition Markov stability (SPMS), a novel, dynamics-based quality metric for graph clustering that offers greater interpretability than existing metrics. SPMS extends the ideas of traditional Markov stability to soft clusterings by describing the rate at which communities trap random walkers on the graph for a fixed time, while explicitly integrating information about cluster inhomogeneity. We argue that SPMS is a suitable objective function for graph clustering and analyze how the spectrum of the underlying graph influences its behavior. In our algorithmic framework, we describe a clustering with a set of localized probability distributions, which we call a soft partition, and maximize SPMS over the space of soft partitions to obtain a nuanced description of the community structure. The optimal soft partition yields information about intra-cluster degree inhomogeneity and naturally identifies ambiguous nodes, which may intuitively belong to multiple clusters or none at all. We describe an efficient method to optimize SPMS and demonstrate its empirical success on model graphs and large, real-world datasets. Finally, we propose and test a downstream algorithm for identifying core-periphery substructure within clusters.