Spectral clustering of directed and time-evolving graphs : theory and applications
| dc.contributor.advisor | Klus, Associate Professor Stefan | |
| dc.contributor.author | Trower, Maia | |
| dc.date.accessioned | 2026-02-20T09:30:52Z | |
| dc.date.issued | 2025-08 | |
| dc.description | Spectral clustering of vertices in graphs is well understood for undirected graphs and there exists a wealth of literature on the subject. The method computes a graph Laplacian matrix and groups vertices by projecting them into a lower dimensional space using the eigenvectors of this Laplacian matrix, which contain information about connectivity in the graph. However, standard spectral clustering fails on directed graphs, where relationships between vertices are not necessarily reciprocal and clusters can be characterised in different ways. It is also not obvious how to apply the spectral clustering framework to graphs that evolve in time, as there are many questions to consider about how to represent these graphs and how to define a cluster in this case. This work proposes two extensions to the standard spectral clustering approach, exploiting a connection with dynamical systems theory to consider clusters on graphs as coherent sets using transfer operators. In the case of directed graphs, we propose a Laplacian based on a forward–backward operator which captures dynamics of random walkers on the graph. We illustrate that this is equivalent to the standard approach for undirected graphs as a special case, and numerical results show that this Laplacian outperforms existing approaches for clustering directed graphs in certain parameter settings. A further graph Laplacian is proposed for clustering time-evolving graphs, which draws on canonical correlation analysis and can also be interpreted via dynamical systems. We analyse the performance on benchmarks and show that this Laplacian yields substantial advantages over existing methods. Additionally, a real-world example derived from fluid dynamics is considered and we show that our clustering algorithm can accurately detect fluid patterns evolving in time. | |
| dc.identifier.uri | https://www.ros.hw.ac.uk/handle/10399/5312 | |
| dc.language.iso | en | |
| dc.publisher | Mathematical and Computer Sciences | |
| dc.title | Spectral clustering of directed and time-evolving graphs : theory and applications | |
| dc.type | Doctor of Philosophy |