Spectral clustering of time-evolving networks using the inflated dynamic Laplacian for graphs

Title data

Froyland, Gary ; Kalia, Manu ; Koltai, Peter:
Spectral clustering of time-evolving networks using the inflated dynamic Laplacian for graphs.
arXiv , 2024
DOI: https://doi.org/10.48550/arXiv.2409.11984

Official URL:

Abstract in another language

Complex time-varying networks are prominent models for a wide variety of spatiotemporal phenomena. The functioning of networks depends crucially on their connectivity, yet reliable techniques for determining communities in spacetime networks remain elusive. We adapt successful spectral techniques from continuous-time dynamics on manifolds to the graph setting to fill this gap. We formulate an inflated dynamic Laplacian for graphs and develop a spectral theory to underpin the corresponding algorithmic realisations. We develop spectral clustering approaches for both multiplex and non-multiplex networks, based on the eigenvectors of the inflated dynamic Laplacian and specialised Sparse EigenBasis Approximation (SEBA) post-processing of these eigenvectors. We demonstrate that our approach can outperform the Leiden algorithm applied both in spacetime and layer-by-layer, and we analyse voting data from the US senate (where senators come and go as congresses evolve) to quantify increasing polarisation in time.

Further data

Item Type:	Preprint, postprint
Institutions of the University:	Faculties Faculties > Faculty of Mathematics, Physics und Computer Science Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data > Chair Dynamical Systems and Data - Univ.-Prof. Dr. Peter Koltai Research Institutions > Central research institutes > Research Center for AI in Science and Society Research Institutions Research Institutions > Central research institutes
Result of work at the UBT:	Yes
DDC Subjects:	500 Science > 510 Mathematics
Date Deposited:	24 Oct 2024 05:38
Last Modified:	05 Nov 2025 08:20
URI:	https://eref.uni-bayreuth.de/id/eprint/90815