Weighted complement graphs of spatial networks with functional connections reveal nodes with high potential for new links
Tina Šfiligoj ∗, Oded Cats · 2026
Read Weighted complement graphs of spatial networks with functional connections reveal nodes with high potential for new links by Tina Šfiligoj ∗, Oded Cats (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21528.txt.
Introduction
Tina Šfiligoj and Oded Cats study unrealised transport networks through weighted complement graphs. A complement graph links unlinked nodes, but its edge weights cannot be fixed. Travel times as edge weights impose constraints, so the authors build complement graphs from distances between stops, combined with network velocity and waiting-time distributions. The most central nodes in the complement graph are not the least central in the original but those at the centre lacking topological links. Tests on 31 metro networks worldwide confirm this as a spatial effect.
Catalog record
| CREATOR | Tina Šfiligoj ∗, Oded Cats |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47050 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.21528
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Weighted complement graphs of spatial networks with functional connections reveal nodes with high potential for new links Tina Šfiligoj ∗, Oded Cats Abstract Abstract 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 \overline{G} of an unweighted graph G is a straightforward concept, yielding a graph on the same set of nodes, and an edge exists in \overline{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. Keywords: public transport, network science, node centrality, complement graph, spatial network 1 Introduction The analysis of node importance in spatial networks [ 3 ] , and in network analysis in general, often focuses on identifying the most important nodes in the network, which correspond to critical locations in the network, be it stops in public transport networks or junctions in road networks, among others. The node importance is measured by any of the numerous centrality measures, among which the most common are degree, closeness, betweenness and eigenvector centrality. The highest centrality nodes are those with the greatest influence on various important phenomena on networks, such as robustness or vulnerability (e.g., [ 14 , 11 , 21 ] ), or identifying the most influential spreaders (e.g., [ 15 , 22 , 12 ] ). In real-world spatial networks, such as transportation networks, the topology itself is often not a sufficient descriptor of the system due to its geographical embeddedness and the geometrical properties of the geographical space. The inclusion of infrastructural or operational properties, which are added as edge weights (e.g., travel times or service frequency), has consistently been shown to more accurately reflect the actual behaviour of the system, including the assessment of node importance (e.g., [ 16 , 25 ] . Including edge weights in the models introduces non-trivial relations between node importance in unweighted networks and their weighted counterparts (e.g., node degree vs. strength, or betweenness centrality with travel cost on the links vs. unweighted edges) (e.g., [ 20 , 19 ] ). This is especially prominent in spatial networks where the edge weights, representing travel costs (distance or travel time), are constrained based on the physical embeddedness of the network. These relationships are often non-linear, indicating a complex interplay between topology and space [ 2 , 3 ] . Understandably, past work has heavily focused on investigating the most central and thereby important nodes. Less central nodes could have their lack of centrality attributed to either spatial features (e.g., peripheral location) or network features (e.g., poor connectivity despite a geographically favourable location). We argue here that the distinction between these two categories is important and consequential for network development. Notably, the nodes in the latter category may be currently unimportant for the prevailing network structure but not unimportant when considering potential future network states. In the area of transport networks, [ 4 ] and [ 8 ] considered road networks and identified the least important nodes according to betweenness centrality, which they called the topological periphery. They found that the least important nodes fall into two categories: those at the geographical periphery and poorly connected nodes in the geographical centres (often representing cul-de-sacs). Moreover, the shortest paths connecting the least topologically important but geographically central nodes are those with the highest circuity, indicating significant inefficiencies in the network. While this work differs from our approach in considering road networks with their inherent restrictions to planarity, it offers an interesting result which we comment on in the Discussion section. Public transport networks (PTN) are a prominent class of spatial networks, with stops embedded in a geographical space that imposes physical constraints on system operation. Even in the theoretical ideal case without resource constraints, the geographical distance between a pair of nodes poses an upper limit on the minimum travel time between them, as the maximum velocity and acceleration along a link are bounded by technology, traffic and passenger safety concerns. This embeddedness, together with the actual PTN infrastructure and service frequencies, sets the feasible ranges of travel times, which are often included as edge weights in PTN modelling. Although there is a large body of literature on the interplay between topology and geography in spatial networks, related work mostly considers planar networks that represent network infrastructure. In PTNs, this is the so-called L-space [ 30 ] , or space-of-infrastructure representation [ 16 ] , in which two node share an edge if they represent consecutive stops on a line. In comparison, spatial networks with functional connections are less common in the literature. By functional connections, we mean any relation between nodes stemming either from operational features of the network, such as line operations, or dynamics on networks, such as passenger flows. Such edges carry a level of spatial abstraction, in that they give rise to highly non-planar structures. In PTN analysis, a widely-used representation is the so-called P-space representation [ 30 ] , or space-of-service [ 16 ] , where nodes represent stops, and there is an edge between two nodes if the corresponding stops lie on the same line. In other words, each line is a clique, and paths in this representation effectively count the number of transfers. Edge weights in P-space often represent service frequencies, which can be translated into average waiting times. In addition, from the underlying infrastructure, in-vehicle times along P-space edges can be computed from the corresponding paths in the infrastructural representation; thus, we can obtain total travel times between all pairs of nodes. Such non-planar networks can have high edge densities, and in the P-space, any - existing or potential - edge is understood in terms of the two stops sharing a line. In this representation, the absence of an edge does not imply a physical impossibility but rather an unrealised direct connection. This leads us to ask: can we gain original insights into the network properties by systematically analysing the unrealised part of the network? i.e. all the services/connections that could have existed but are not included in the current PTN. In doing so, we encountered and addressed an additional research question: how can we use the spatial embeddedness of the network to estimate possible weighted realisations of currently non-existing edges? We approach the problem by considering complement graphs of the functional representations of spatial networks. Given a graph G(V,E) with a node set V and an edge set