Geometric organization and inference of shortest path nodes in soft random geometric graphs

Journal Article (2026)
Author(s)

Z. Qiu (TU Delft - Electrical Engineering, Mathematics and Computer Science)

G.S. Balogh (TU Delft - Electrical Engineering, Mathematics and Computer Science, Alfréd Rényi Institute of Mathematics)

X. Liu (TU Delft - Electrical Engineering, Mathematics and Computer Science)

P.F.A. Van Mieghem (TU Delft - Electrical Engineering, Mathematics and Computer Science)

M.A. Kitsak (Indiana University Bloomington, TU Delft - Electrical Engineering, Mathematics and Computer Science)

Research Group
Network Architectures and Services
DOI related publication
https://doi.org/10.1103/dq2j-z8k6 Final published version
More Info
expand_more
Publication Year
2026
Language
English
Research Group
Network Architectures and Services
Journal title
Physical Review Research
Issue number
3
Volume number
8
Article number
033149
Page Views
60
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

The shortest path problem is related to many dynamic processes on networks, ranging from routing in communication networks to signaling in molecular interaction networks. When the network is fully known, the shortest path problem can be solved precisely and in polynomial time. If, however, the network of interest is only partially observable, the shortest path problem is no longer straightforward. Inspired by the shortest path problem in partially observable networks, we investigate the geometric properties of shortest paths in Euclidean soft random geometric graphs (SRGGs). We find that shortest paths are aligned along geodesic curves connecting shortest path end points. The strength of the shortest path alignment, as quantified by the average distance to geodesic from shortest path nodes and the average path stretch, is higher for larger SRGGs with short-range connections. In addition, we find that the strength of the shortest path alignment is nonmonotonic with respect to the average degree of the SRGG. Based on these observations, we establish the conditions under which the alignment of shortest paths may be sufficiently strong to allow the identification of shortest path nodes based on their proximity to geodesic curves. We show that in partially observable networks with uncertain node positions, our geometric approach can outperform network-based shortest path algorithms. In practical settings, our findings may have applications to navigation, wireless routing, and flow characterization in infrastructure networks.