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^{\chi }$, while the transversal fluctuations, known as wandering, grow as $L^{\xi }$. 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 $\xi =3/5$ and $\chi =1/5$, or $\xi =7/10$ and $\chi =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 $\xi =0.60\pm 0.01$ and $\chi =0.20\pm 0.01$, showing a theoretical minimal wandering. The second class contains graphs based on excluded regions such as $\beta$ skeletons and the Delaunay triangulation and are characterized by the values $\xi =0.70\pm 0.01$ and $\chi =0.40\pm 0.01$, with a nearly theoretically maximal wandering exponent. We also show numerically that the so-called Kardar-Parisi-Zhang (KPZ) relation $\chi =2\xi -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.

Figure 1

Illustration of the problem on a small network. The network is constructed over a set of points denoted by circles here and the edges are denoted by lines. For a pair of nodes $(x,y)$ we look for the shortest path (shown here by a dotted line) where the length of the path is given by the sum of all edges length: $d(x,y)=|x-a|+|a-b|+|b-c|+|c-d|+|d-y|$.

Figure 2

Spatial networks, each built on a different realization of a simple, stationary Poisson point processes of expected $\rho =1000$ points in the unit square $\mathcal{V}={[-1/2,1/2]}^2$ but with different connection laws. The boundary points at time $t=1/2$ of the first-passage process are shown in red, while their respective geodesics are shown in blue. (a) Hard RGG with unit disk connectivity. (b) Soft RGG with Rayleigh fading connection function $H\left(r\right)=exp(-\beta r^2)$; (c) 7-NNG; (d) relative neighborhood graph, which is the lune-based $\beta$ skeleton for $\beta =2$; (e) Gabriel graph, which is the lune-based $\beta$ skeleton for $\beta =1$; and (f) the Delaunay triangulation.

Figure 3

Example Euclidean geodesics (blue) running between two end nodes of a simple, stationary Poisson point process (red). The maximal transversal deviation is shown (vertical black line). The Euclidean distance between the endpoints is the horizontal black line. The PPP density is equal for each model. (a) Hard RGG, (b) soft RGG with connectivity probability $H\left(r\right)=exp(-r^2)$, (c) 7-NNG, (d) RNG, (e) GG, and (f) DT.

Figure 4

The geometry of the lune-based $\beta$ skeleton for (a) $\beta =1/2$, (b) $\beta =1$, and (c) $\beta =2$. For $\beta <1$, nodes within the intersection of two disks each of radius $|x-y|/2\beta$ preclude the edges between the disk centers, whereas for $\beta >1$, we use instead radii of $\beta |x-y|/2$. Thus, whenever two nodes are nearer each other than any other surrounding points, they connect and otherwise do not.

Figure 5

The three statistics we observe, expected travel time (a) and (d), expected wandering (b) and (e), and standard deviation of the travel time (c) and (f). The power-law exponents are indicated in the legend. Error bars of one standard deviation are shown for each point. The top plots show the results from the models in first universality class, while the lower plots show the second class. The RGG and NNG are distinguished with different colours (green and blue), as are EFPP on the complete graph, the DT, and the two $\beta$ skeletons (Gabriel graph and relative neighborhood graph). The point process density $\rho$ points per unit area is given for each model.

Figure 6

Travel-time distributions for the DT [(a)–(c)], RNG [(d)–(f)], and Gabriel [(g)–(i)] graphs, compared with the GUE and GSE Tracy-Widom ensembles, and the Gaussian distribution. The point process density $\rho$ points per unit area is given for each model. The slight skew of the TW distribution is not present in the data.

Figure 7

Skewness (a) and kurtosis (b), for the travel-time fluctuations, computed for each network model. For a Gaussian distribution, the skewness is 0 and the kurtosis equal to 3, values that we indicate by dashed black lines. The point process density $\rho$ points per unit area is given for each model. The Tracy-Widom distribution has only marginally different moments to the normal, also shown by dashed black lines, with labels added to distinguish each specific distribution (GOE, GUE, or GSE), as well as the Gaussian.

Figure 8

Transversal fluctuations of the geodesics in all models (colored points) and compared with the fluctuations of a continuous Brownian bridge process between the same end points (red dashed curve). The point process density $\rho$ points per unit area is given for each model.