Shape of shortest paths in random spatial networks.

In the classic model of first-passage percolation, for pairs of vertices separated by a Euclidean distance L, geodesics exhibit deviations from their mean length L that are of order L^{χ}, while the transversal fluctuations, known as wandering, grow as L^{ξ}. We find that when weighting edges directly with their Euclidean span in various spatial network models, we have two distinct classes defined by different exponents ξ=3/5 and χ=1/5, or ξ=7/10 and χ=2/5, depending only on coarse details of the specific connectivity laws used. Also, the travel-time fluctuations are Gaussian, rather than Tracy-Widom, which is rarely seen in first-passage models. The first class contains proximity graphs such as the hard and soft random geometric graph, and the k-nearest neighbor random geometric graphs, where via Monte Carlo simulations we find ξ=0.60±0.01 and χ=0.20±0.01, showing a theoretical minimal wandering. The second class contains graphs based on excluded regions such as β skeletons and the Delaunay triangulation and are characterized by the values ξ=0.70±0.01 and χ=0.40±0.01, with a nearly theoretically maximal wandering exponent. We also show numerically that the so-called Kardar-Parisi-Zhang (KPZ) relation χ=2ξ-1 is satisfied for all these models. These results shed some light on the Euclidean first-passage process but also raise some theoretical questions about the scaling laws and the derivation of the exponent values and also whether a model can be constructed with maximal wandering, or non-Gaussian travel fluctuations, while embedded in space.