Weighted complement graphs of spatial networks with functional connections reveal nodes with high potential for new links
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914502143901696 |
|---|---|
| author | Šfiligoj, Tina Cats, Oded |
| author_facet | Šfiligoj, Tina Cats, Oded |
| contents | In this study, we take a systematic look at the unrealised part of public transport networks (PTNs) with functional connections. We consider their complement graphs and study their structure. The complement graph $\bar G$ of an unweighted graph $G$ is a straightforward concept, yielding a graph on the same set of nodes, and an edge exists in $\bar G$ if and only if it is not present in $G$. In contrast, a weighted complement graph cannot be uniquely determined. However, if we consider PTNs with travel times as edge weights, there are physical constraints on the possible weight ranges. We propose a method to construct weighted complement graphs of operational PTN graph representations based on the geographical distances between nodes (representing stops) and assign weights to edges based on distance, combined with network-specific distributions of effective velocities and waiting times. We observe that the most central nodes in the weighted complement graph do not correspond to the least central nodes in the original network but are, remarkably, those in the geographical centre of the network that lack topological connectedness. Testing against null models on a dataset of 31 metro networks worldwide confirms that this is a fundamentally spatial effect. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21528 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Weighted complement graphs of spatial networks with functional connections reveal nodes with high potential for new links Šfiligoj, Tina Cats, Oded Physics and Society In this study, we take a systematic look at the unrealised part of public transport networks (PTNs) with functional connections. We consider their complement graphs and study their structure. The complement graph $\bar G$ of an unweighted graph $G$ is a straightforward concept, yielding a graph on the same set of nodes, and an edge exists in $\bar G$ if and only if it is not present in $G$. In contrast, a weighted complement graph cannot be uniquely determined. However, if we consider PTNs with travel times as edge weights, there are physical constraints on the possible weight ranges. We propose a method to construct weighted complement graphs of operational PTN graph representations based on the geographical distances between nodes (representing stops) and assign weights to edges based on distance, combined with network-specific distributions of effective velocities and waiting times. We observe that the most central nodes in the weighted complement graph do not correspond to the least central nodes in the original network but are, remarkably, those in the geographical centre of the network that lack topological connectedness. Testing against null models on a dataset of 31 metro networks worldwide confirms that this is a fundamentally spatial effect. |
| title | Weighted complement graphs of spatial networks with functional connections reveal nodes with high potential for new links |
| topic | Physics and Society |
| url | https://arxiv.org/abs/2604.21528 |