CS Paper Radar

Edge-based Katz centralities for spatio-temporal multiplex networks

Kai Bergermann, Francesco Gravili, Valeria Simoncini, Martin Stoll

cs.SI math.NA ·submitted 2026-09-21 14:17 UTC · v2

Abstract

Katz centrality is a well-established measure to identify and rank the most important nodes in complex networks by means of a linear system solve. Recent works have developed notions of Katz centrality for temporal, i.e., time-evolving networks. Their drawback is that small changes in the network structure may drastically change centralities across large parts of the network. Moreover, an unproportional effort in the network science community has been devoted to the study of node-based quantities while edge-based measures are far less explored. In this manuscript, we introduce a novel failure-aware temporal multiplex network model for computing edge-based Katz centralities for spatial networks. This class of networks admits the use of the line graph as network representation. We use a block-triangular and -banded supra-adjacency matrix representation, modeling inter-layer connections as low-rank matrices, which assigns a spatially constrained emphasis on up- or downdated edges. These could represent, e.g., breakages of water/gas pipes or obstructions in street networks in real-time infrastructure monitoring applications. We analyze the structure of the of the block matrix inverse with respect to entry decay in the blocks above the block-diagonal. This gives rise to two truncation approaches that allow drastic computational runtime reductions at the cost of introducing a controlled truncation error. Numerical experiments on a range of real-world spatio-temporal networks of size up to $2\cdot 10^8$ illustrate accuracy and efficiency with runtime gains of up to a factor of $679$.

Closest papers

Nearest neighbours by meaning across the whole index.

Spectral Efficiency Centrality: An Efficient Spectral Approach for Influential Node Identification in Temporal Networks

cs.SI ·2026-08-14 ·Aksa Urooj, Iqra Altaf Gillani
similarity 0.62
Abstract · 23 pages, 16 figures, 11 tables, journal paper

Centrality measures play a vital role in identifying influential nodes in evolving networks. While existing temporal centrality measures primarily rely on local structural properties or temporal paths, spectral node-removal approaches have been largely limited to static networks. To bridge this gap, we propose Spectral Efficiency Centrality (SEC), a temporal spectral centrality framework that quantifies node importance by evaluating the change in spectral radius caused by node removal across temporal snapshots. By capturing the global structural influence of nodes throughout network evolution, SEC identifies nodes that are critical for preserving the structural connectivity and efficiency of temporal networks. To improve computational scalability, we further develop an efficient approximation, ASEC, based on Perron-Frobenius theory and first-order eigenvalue perturbation. ASEC requires only the leading eigenpair and avoids repeated eigendecomposition, making it suitable for large temporal networks. Extensive experiments on multiple real-world temporal datasets demonstrate that SEC and ASEC outperform existing baseline centrality measures in identifying influential nodes under SI, SIS, and IC diffusion models. Statistical significance and robustness analyses further confirm their effectiveness, while ASEC offers a computationally efficient solution for large-scale temporal networks.

0.10

Dynamic Centrality Measures for Water Distribution Network Hydraulics

eess.SY math.OC ·2026-09-09 ·MirSaleh Bahavarnia, Salma M. Elsherif, Ahmad F. Taha
similarity 0.58
Abstract

Water distribution networks (WDNs) are susceptible to various failures, including but not limited to human errors, cyber-attacks, and network modifications, necessitating the vulnerability analysis of WDNs. Graph-theoretic centrality measures---as a main class of centrality measures---aim to rank the network components solely based on their influence (i.e., criticality) on the WDN topology in the case of input changes, while overlooking the WDN dynamics. To overcome such a limitation, this paper uses a control-theoretic centrality measure to identify the network's most and least influential pipes in WDNs, by simultaneously incorporating the dynamics and topology of the WDN. First, given a WDN modeled by nonlinear differential-algebraic equations (NDAEs) consisting of transient flow dynamics as differential equation (DE) and conservation of water mass as algebraic equation (AE) and considering the pipe flow rates as states of the state-space (SS) representation, we extract a linearized system modeled by linear ordinary differential equations (LODEs) around the equilibrium (i.e., steady) flow rate vector. Second, treating pipe flow rates as SS nodes (states), we introduce a node centrality-based measure, namely \textit{vulnerability vector (VV)}, to rank the network pipes based on their influence on the dynamics and topology of the WDN in the case of input changes. In particular, the network's most and least influential pipes can be identified through such a centrality-based approach. This enables water engineers to understand the WDN's vulnerability better and effectively prioritize the maintenance and operational efforts on the most influential pipes within the WDN.

0.25

Semi-Monotonicity for Spectral Centrality Measures

cs.SI ·2026-09-21 ·Paolo Boldi, Davide D'Ascenzo, Flavio Furia, Sebastiano Vigna
theory similarity 0.57
Abstract

Score monotonicity and rank monotonicity are properties describing the behavior of a centrality measure when an arc is added to a network: the former requires that the score of the target of the arc should increase, the latter that its importance with respect to the remaining nodes should not deteriorate. While in directed networks almost all classical centrality measures satisfy both properties, in undirected networks they fail for most measures: adding an edge can reduce the score or the rank of one of its endpoints. Semi-monotonicity is a recently introduced weaker property for undirected networks, requiring that at least one of the two endpoints of the new edge enjoys monotonicity, and it is known to hold for closeness, harmonic centrality, distance-decay centralities and betweenness. In this paper we study semi-monotonicity for three classical spectral centrality measures: eigenvector centrality, Katz's index, and PageRank. We prove that all of them are strictly rank semi-monotone on connected undirected graphs, and that all of them are also score semi-monotone, (the only exception being eigenvector centrality when scores are normalized by projecting the constant vector on the dominant eigenspace, for which we provide a counterexample). In particular, adding an edge can never decrease the PageRank of both its endpoints, which answers a question left open in previous work.

0.19

Spectral Fingerprints of Street-Network Morphology: A Size-Adjusted Graph-Laplacian Descriptor of Urban Fabric

cs.SI physics.soc-ph ·2026-08-17 ·Piotr C. Kaminski
similarity 0.57
Abstract · 18 pages, 7 figures. Under review at Journal of Complex Networks (Oxford University Press)

Decades of space-syntax research have established that the topology of the street network conditions movement, co-presence and urban activity. The standard vocabulary for this -- integration, choice and connectivity -- summarises each street's position as a scalar centrality, yet two streets with identical centrality can sit in radically different morphological fabric. We introduce a compact, comparable, machine-learning-ready encoding of that local fabric: the spectral fingerprint, a fixed-dimensional kernel-density representation of the graph-Laplacian eigenvalue distribution of each node's k-hop ego subgraph, computed on the COINS dual graph of the street network. From it we derive two interpretable scalar readouts: the Mesh Index (MI), a normalised spectral entropy, and the Connectivity Resilience Index (CRI), the algebraic connectivity (Fiedler value). Both are corrected for an ego-subgraph-size confound that dominates raw spectral statistics. Applied to the full street network of Poznan, Poland (1,908 continuity-based strokes), the descriptor is robust to its encoding hyperparameters (spectral resolution and kernel bandwidth; Spearman rho >= 0.98) while remaining scale-dependent in its neighbourhood radius. The size adjustment leaves the Mesh Index near-orthogonal to integration (r = 0.06), carrying information classical centrality does not. The fingerprint separates morphological tissue types without supervision, and the Mesh Index is associated with the functional diversity of street-adjacent activity at the neighbourhood scale (r ~ 0.19, on open OpenStreetMap data). We delineate the method's scope honestly: it characterises what kind of activity a street's position affords, not the price that activity commands. It offers an information-theoretic morphological descriptor that complements space syntax and is directly consumable by modern graph-learning pipelines.

0.25

Decompose Dynamics Before Learning Dependencies in Spatiotemporal Systems

cs.CE ·2026-09-29 ·Ziqi Wang, Daojiang Hu, Cheng Bao, Zhiwei Ling, Wenzhuo Qian +2 more
similarity 0.56
Abstract

Relations in networked spatiotemporal systems are often learned from observations that entangle dynamics governed by different mechanisms, obscuring what evolves locally and how it propagates across nodes. We introduce Component-Aware Network Dynamics with Ordered Relations (CANDOR), which decomposes local dynamics before learning their dependencies. CANDOR represents each trajectory through a persistent background, gradual accumulation and release, and sparse shocks. Conditioned on these components, a delay-aware physical branch models edge and sample-dependent propagation over directed topology, while a topology-unconstrained functional branch discovers latent dependencies from background dynamics. Context-adaptive fusion combines functional, forward-propagation, and reverse-support forecasts, with training objectives encouraging specialized and semantically consistent representations. Experiments on two traffic benchmarks and three long-horizon water-quality datasets span two distinct spatiotemporal systems: human-driven urban traffic and naturally evolving river water quality. CANDOR achieves the lowest aggregate normalized error across five datasets, outperforming the overall runner-up by 7.25%. These results establish decomposition before dependency learning as an effective principle for spatiotemporal representation learning.

0.21

Theoretical relations between basic centrality measures in real-world networks

cs.SI math.CO ·2026-11-01 ·Mikhail Tuzhilin
similarity 0.56
Abstract

We establish new relationships among several fundamental measures of real-world networks, including the average clustering coefficient, the global clustering coefficient, the average shortest-path length and degree centrality, closeness centrality, betweenness centrality and ksi-centrality. We further develop the theory of $j$-neighborhood centrality, which encompasses degree centrality and ksi-centrality as special cases.

0.14

Computational Structure of Pairwise Housing Connectedness Networks

cs.CE cs.SI ·2026-11-09 ·Seo In Jang, Seung Ho Choi, Ji-Eun Shin, Hyunwoo Lee
similarity 0.55
Abstract · 56 pages, 6 figures, 16 tables; includes supplementary information

Directed housing-submarket networks combine common market movement with heterogeneous bilateral relations, and different node-level measures need not yield distinct empirical rankings. We construct a positive pairwise net-connectedness network from the generalized forecast error variance decomposition (GFEVD) of a vector autoregression (VAR) and use it to compare complementary node positions. Net directional connectedness (NET), PageRank, and Viral Centrality summarize net directional balance, recursively weighted incoming position, and normalized multistep reach. When bilateral net differences are nonzero, the network is a weighted tournament. A least-squares edge-flow decomposition separates the pairwise-net matrix into a NET-equivalent gradient component and a NET-orthogonal residual, while a monotone-allocation condition establishes exact PageRank-indegree correspondence in a transitive tournament. In Seoul's 25-district network, the gradient component accounts for 70.9% of the squared Frobenius norm, leaving 29.1% in the residual component. PageRank is strongly aligned with indegree (Spearman $ρ=0.987$), and Viral Centrality with outdegree ($ρ=0.935$); the PageRank alignment exceeds the range of independently weighted simulations with comparable tournament consistency and edge-weight variation. Three common-component treatments reduce total connectedness from 81.98% to 50.60-52.00%, a 36.6-38.3% reduction relative to the raw system, and reverse 97-98 of 300 pairwise net directions. Thus, both the magnitude and the apparent direction of connectedness depend materially on the treatment of citywide common movement. Songpa's positive NET position remains prominent across common-component treatments and dynamic specifications and ranks first in both chronological subsamples.

0.34

A Graph Neural Network Surrogate Model for Incident-Based Travel Time Prediction Under Limited Sensor Data

cs.CE ·2026-09-13 ·Abhilasha Saroj, Natalie Myers, Haoran Niu
similarity 0.55
Abstract

Localized roadway incidents can produce congestion well beyond their point of origin, but evaluating these effects with microscopic simulation requires a separate run for each scenario. This paper presents a Spatio-Temporal Graph Convolutional Network (STGCN) for forecasting route-level travel times on a simulated Nashville, Tennessee road network with 1,037 junctions and 1,601 road segments. The model uses directional traffic counts from only 129 signalized intersections, reflecting data commonly available to transportation agencies. By representing these intersections as a graph, the STGCN jointly captures spatial dependence and temporal traffic evolution to learn how localized disruptions propagate through the network. We compare a baseline trained on 80 incident-free simulations with an incident-inclusive model trained with an additional 360 lane-blockage scenarios across 12 locations and three durations. The baseline achieved a relative mean absolute error (MAE) of 9.94%. The incident-inclusive model achieved 9.67% overall, 6.45% during active incidents, and 13.62% at 30 incident locations withheld entirely from training. On disrupted routes, its predictions were within 2.0 minutes of observed travel time on average. For comparison, simulated travel times vary by 7.4%, or 1.3 minutes, across random seeds under identical conditions. Inference requires approximately 53 ms on a single CPU core, demonstrating the potential of the model as an efficient surrogate for transportation resilience screening, incident management, and proactive rerouting.

0.17