Koskin, Vladimir;
Kells, Adam;
Clayton, Joe;
Hartmann, Alexander;
Annibale, Alessia;
Rosta, Edina;
(2022)
Variational Kinetic Clustering of Complex Networks.
The Journal of Chemical Physics
10.1063/5.0105099.
(In press).
Preview |
PDF
Efficient_Kinetic_Clustering_of_High_Dimensional_Networks_combined_final.pdf - Accepted Version Download (2MB) | Preview |
Abstract
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.
| Type: | Article |
|---|---|
| Title: | Variational Kinetic Clustering of Complex Networks |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1063/5.0105099 |
| Publisher version: | https://doi.org/10.1063/5.0105099 |
| Language: | English |
| Additional information: | This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Physics and Astronomy UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10155428 |
Archive Staff Only
 |
View Item |
