The shape of shortest paths in random spatial networks
arXiv:1906.04314 · doi:10.1103/PhysRevE.100.032315
Abstract
In the classic model of first passage percolation, for pairs of vertices separated by a Euclidean distance , geodesics exhibit deviations from their mean length that are of order , while the transversal fluctuations, known as wandering, grow as . 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 and , or and , 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 -nearest neighbour random geometric graphs, where via Monte Carlo simulations we find and , showing a theoretical minimal wandering. The second class contains graphs based on excluded regions such as -skeletons and the Delaunay triangulation and are characterised by the values and , with a nearly theoretically maximal wandering exponent. We also show numerically that the KPZ relation 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.
arXiv comment15 pages, 7 figures
References in corpus (29)
- Classes of behavior of small-world networks
- Spatial Networks
- Centrality Measures in Spatial Networks of Urban Streets
- Navigability of Complex Networks
- Universal Fluctuations of Growing Interfaces: Evidence in Turbulent Liquid Crystals
- Growing interfaces uncover universal fluctuations behind scale invariance
- An exact solution for the KPZ equation with flat initial conditions
- Optimal Paths in Disordered Complex Networks
- From the betweenness centrality in street networks to structural invariants in random planar graphs
- Network geometry with flavor: from complexity to quantum geometry
- Beyond the clustering coefficient: A topological analysis of node neighbourhoods in complex networks
- Connectivity of soft random geometric graphs
- Spatial preferential attachment networks: Power laws and clustering coefficients
- First passage percolation on random graphs with finite mean degrees
- Connected Spatial Networks over Random Points and a Route-Length Statistic
- Universality for mathematical and physical systems
- Network Geometry and Complexity
- Full Connectivity: Corners, edges and faces
- Universal behavior of optimal paths in weighted networks with general disorder
- New horizons in multidimensional diffusion: The Lorentz gas and the Riemann Hypothesis
- Large complex correlated Wishart matrices: Fluctuations and asymptotic independence at the edges
- Connectivity of Soft Random Geometric Graphs Over Annuli
- Topology and the Kardar-Parisi-Zhang universality class
- Random geometry and the Kardar-Parisi-Zhang universality class
- Betweenness Centrality in Dense Random Geometric Networks
- A simplified proof of the relation between scaling exponents in first-passage percolation
- Which Connected Spatial Networks on Random Points have Linear Route-Lengths?
- Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition
- Counting Geodesic Paths in 1D VANETs
Cited by in corpus (8)
- Betweenness centrality in dense spatial networks
- Random geometric graphs in high dimension
- Sizing the length of complex networks
- An Introduction to Complex Networks in Climate Finance
- Explosive dismantling of two-dimensional random lattices under betweenness centrality attacks
- First-Passage Percolation under extreme disorder: from bond-percolation to Kardar-Parisi-Zhang universality
- Vulnerability of Transport through Evolving Spatial Networks
- Connectivity of 1d random geometric graphs