Variational Kinetic Clustering of Complex Networks

Vladimir Koskin, Adam Kells, Joe Clayton, Alexander K Hartmann, Alessia Annibale*, Edina Rosta*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
8 Downloads (Pure)


Efficiently identifying the most important communities and key transition nodes in weighted and unweighted networks is a prevalent problem in a wide range of disciplines. Here we focus on the optimal clustering using variational kinetic parameters, linked to Markov processes defined on the underlying networks, namely the slowest relaxation time and the Kemeny constant. We derive novel relations in terms of mean first passage times for optimizing clustering via the Kemeny constant, and show that the optimal clustering boundaries
have equal round-trip times to the clusters they separate. We also propose an efficient method that first projects the network nodes onto a 1D reaction coordinate and subsequently performs a variational boundary
search using a parallel tempering algorithm, where the variational kinetic parameters act as an energy function to be extremized. We find that maximization of the Kemeny constant is effective in detecting communities, while the slowest relaxation time allows for detection of transition nodes. We demonstrate the validity of our method on several test systems, including synthetic networks generated from the stochastic block model and real world networks (Santa Fe Institute collaboration network, a network of co-purchased political books, and a street network of multiple cities in Luxembourg). Our approach is compared with existing clustering algorithms based on modularity and the Robust Perron Cluster Analysis and the identified transition nodes
are compared with different notions of node centrality.
Original languageEnglish
Article number104112
JournalJournal of Chemical Physics
Issue number10
Early online date14 Mar 2023
Publication statusPublished - 14 Mar 2023


Dive into the research topics of 'Variational Kinetic Clustering of Complex Networks'. Together they form a unique fingerprint.

Cite this