Geometric Organization and Inference of Shortest Path Nodes in Soft Random Geometric Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910011596210176 |
|---|---|
| author | Qiu, Zhihao Balogh, Sámuel G. Liu, Xinhan Van Mieghem, Piet Kitsak, Maksim |
| author_facet | Qiu, Zhihao Balogh, Sámuel G. Liu, Xinhan Van Mieghem, Piet Kitsak, Maksim |
| contents | 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 {\it Euclidean} Soft Random Geometric Graphs (SRGGs). We find that shortest paths are aligned along geodesic curves connecting shortest path endpoints. 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 non-monotonic 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04507 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Geometric Organization and Inference of Shortest Path Nodes in Soft Random Geometric Graphs Qiu, Zhihao Balogh, Sámuel G. Liu, Xinhan Van Mieghem, Piet Kitsak, Maksim Physics and Society Data Analysis, Statistics and Probability 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 {\it Euclidean} Soft Random Geometric Graphs (SRGGs). We find that shortest paths are aligned along geodesic curves connecting shortest path endpoints. 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 non-monotonic 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. |
| title | Geometric Organization and Inference of Shortest Path Nodes in Soft Random Geometric Graphs |
| topic | Physics and Society Data Analysis, Statistics and Probability |
| url | https://arxiv.org/abs/2602.04507 |