Cluster Persistence for Weighted Graphs
Persistent homology is a natural tool for probing the topological characteristics of weighted graphs, essentially focusing on their 0-dimensional homology. While this area has been thoroughly studied, we present a new approach to constructing a filtration for cluster analysis via persistent homology...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-11-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/25/12/1587 |
| _version_ | 1797381190621069312 |
|---|---|
| author | Omer Bobrowski Primoz Skraba |
| author_facet | Omer Bobrowski Primoz Skraba |
| author_sort | Omer Bobrowski |
| collection | DOAJ |
| description | Persistent homology is a natural tool for probing the topological characteristics of weighted graphs, essentially focusing on their 0-dimensional homology. While this area has been thoroughly studied, we present a new approach to constructing a filtration for cluster analysis via persistent homology. The key advantages of the new filtration is that (a) it provides richer signatures for connected components by introducing non-trivial birth times, and (b) it is robust to outliers. The key idea is that nodes are ignored until they belong to sufficiently large clusters. We demonstrate the computational efficiency of our filtration, its practical effectiveness, and explore into its properties when applied to random graphs. |
| first_indexed | 2024-03-08T20:47:48Z |
| format | Article |
| id | doaj.art-71b70ea13bf14461a66a4ef24c27e82b |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-08T20:47:48Z |
| publishDate | 2023-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-71b70ea13bf14461a66a4ef24c27e82b2023-12-22T14:07:16ZengMDPI AGEntropy1099-43002023-11-012512158710.3390/e25121587Cluster Persistence for Weighted GraphsOmer Bobrowski0Primoz Skraba1School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, UKSchool of Mathematical Sciences, Queen Mary University of London, London E1 4NS, UKPersistent homology is a natural tool for probing the topological characteristics of weighted graphs, essentially focusing on their 0-dimensional homology. While this area has been thoroughly studied, we present a new approach to constructing a filtration for cluster analysis via persistent homology. The key advantages of the new filtration is that (a) it provides richer signatures for connected components by introducing non-trivial birth times, and (b) it is robust to outliers. The key idea is that nodes are ignored until they belong to sufficiently large clusters. We demonstrate the computational efficiency of our filtration, its practical effectiveness, and explore into its properties when applied to random graphs.https://www.mdpi.com/1099-4300/25/12/1587topological data analysisuniversalityclustering |
| spellingShingle | Omer Bobrowski Primoz Skraba Cluster Persistence for Weighted Graphs Entropy topological data analysis universality clustering |
| title | Cluster Persistence for Weighted Graphs |
| title_full | Cluster Persistence for Weighted Graphs |
| title_fullStr | Cluster Persistence for Weighted Graphs |
| title_full_unstemmed | Cluster Persistence for Weighted Graphs |
| title_short | Cluster Persistence for Weighted Graphs |
| title_sort | cluster persistence for weighted graphs |
| topic | topological data analysis universality clustering |
| url | https://www.mdpi.com/1099-4300/25/12/1587 |
| work_keys_str_mv | AT omerbobrowski clusterpersistenceforweightedgraphs AT primozskraba clusterpersistenceforweightedgraphs |