Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910878374297600 |
|---|---|
| author | Trower, Maia Conrad, Nataša Djurdjevac Klus, Stefan |
| author_facet | Trower, Maia Conrad, Nataša Djurdjevac Klus, Stefan |
| contents | Time-evolving graphs arise frequently when modeling complex dynamical systems such as social networks, traffic flow, and biological processes. Developing techniques to identify and analyze communities in these time-varying graph structures is an important challenge. In this work, we generalize existing spectral clustering algorithms from static to dynamic graphs using canonical correlation analysis (CCA) to capture the temporal evolution of clusters. Based on this extended canonical correlation framework, we define the spatio-temporal graph Laplacian and investigate its spectral properties. We connect these concepts to dynamical systems theory via transfer operators, and illustrate the advantages of our method on benchmark graphs by comparison with existing methods. We show that the spatio-temporal graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12864 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian Trower, Maia Conrad, Nataša Djurdjevac Klus, Stefan Social and Information Networks Machine Learning Dynamical Systems Time-evolving graphs arise frequently when modeling complex dynamical systems such as social networks, traffic flow, and biological processes. Developing techniques to identify and analyze communities in these time-varying graph structures is an important challenge. In this work, we generalize existing spectral clustering algorithms from static to dynamic graphs using canonical correlation analysis (CCA) to capture the temporal evolution of clusters. Based on this extended canonical correlation framework, we define the spatio-temporal graph Laplacian and investigate its spectral properties. We connect these concepts to dynamical systems theory via transfer operators, and illustrate the advantages of our method on benchmark graphs by comparison with existing methods. We show that the spatio-temporal graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected graphs. |
| title | Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian |
| topic | Social and Information Networks Machine Learning Dynamical Systems |
| url | https://arxiv.org/abs/2407.12864 |