Scale-invariant random spatial networks

David Aldous (University of California, Berkeley)

Abstract


Real-world road networks have an approximate scale-invariance property; can one devise mathematical models of random networks whose distributions are exactly invariant under Euclidean scaling? This requires working in the continuum plane. We introduce an axiomatization of a class of processes we call "scale-invariant random spatial networks", whose primitives are routes between each pair of points in the plane. We prove that one concrete model, based on minimum-time routes in a binary hierarchy of roads with different speed limits, satisfies the axioms, and note informally that two other constructions (based on Poisson line processes and on dynamic proximity graphs) are expected also to satisfy the axioms. We initiate study of structure theory and summary statistics for general processes in this class.


Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-41

Publication Date: January 28, 2014

DOI: 10.1214/EJP.v19-2920

References

  • Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Highway dimension, shortest paths, and provably efficient algorithms. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 782--793, SIAM, Philadelphia, PA, 2010. MR2809706
  • Aizenman, Michael; Burchard, Almut; Newman, Charles M.; Wilson, David B. Scaling limits for minimal and random spanning trees in two dimensions. Statistical physics methods in discrete probability, combinatorics, and theoretical computer science (Princeton, NJ, 1997). Random Structures Algorithms 15 (1999), no. 3-4, 319--367. MR1716768
  • D. J. Aldous. The continuum random tree. II. An overview. In Stochastic analysis (Durham, 1990), volume 167 of London Math. Soc. Lecture Note Ser., pages 23--70. Cambridge Univ. Press, Cambridge, 1991.
  • Aldous, David J.; Krikun, Maxim. Percolating paths through random points. ALEA Lat. Am. J. Probab. Math. Stat. 1 (2006), 89--109. MR2235175
  • Aldous, David J.; Shun, Julian. Connected spatial networks over random points and a route-length statistic. Statist. Sci. 25 (2010), no. 3, 275--288. MR2791668
  • D.J. Aldous. The shape theorem for route-lengths in connected spatial networks on random points. arXiv:0911.5301v1, 2009.
  • Aldous, David J. More uses of exchangeability: representations of complex random structures. Probability and mathematical genetics, 35--63, London Math. Soc. Lecture Note Ser., 378, Cambridge Univ. Press, Cambridge, 2010. MR2744234
  • Aldous, David J.; Kendall, Wilfrid S. Short-length routes in low-cost networks via Poisson line patterns. Adv. in Appl. Probab. 40 (2008), no. 1, 1--21. MR2411811
  • D. J. Aldous and K. Ganesan. True scale-invariant random spatial networks. Proc. Nat. Acad. Sci. USA, 110:8782--8785, 2013.
  • Bast, Holger; Funke, Stefan; Sanders, Peter; Schultes, Dominik. Fast routing in road networks with transit nodes. Science 316 (2007), no. 5824, 566. MR2313317
  • Benjamini, Itai. Random planar metrics. Proceedings of the International Congress of Mathematicians. Volume IV, 2177--2187, Hindustan Book Agency, New Delhi, 2010. MR2827966
  • Buttazzo, Giuseppe; Pratelli, Aldo; Solimini, Sergio; Stepanov, Eugene. Optimal urban networks via mass transportation. Lecture Notes in Mathematics, 1961. Springer-Verlag, Berlin, 2009. x+150 pp. ISBN: 978-3-540-85798-3 MR2469110
  • Daley, D. J.; Vere-Jones, D. An introduction to the theory of point processes. Vol. II. General theory and structure. Second edition. Probability and its Applications (New York). Springer, New York, 2008. xviii+573 pp. ISBN: 978-0-387-21337-8 MR2371524
  • M. Damron and J. Hanson. Busemann functions and infinite geodesics in two-dimensional first-passage percolation. arXiv:1209.3036, 2012.
  • Durrett, Rick. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2007. x+212 pp. ISBN: 978-0-521-86656-9; 0-521-86656-1 MR2271734
  • R. J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA, January 10, 2004, pages 100--111. SIAM, 2004.
  • J.W. Jaromczyk and G.T. Toussaint. Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 80:1502--1517, 1992.
  • V. Kalapala, V. Sanwalani, A. Clauset, and C. Moore. Scale invariance in road networks. Phys. Rev. E, 73(2):026130, Feb 2006.
  • W. S. Kendall. From Random Lines to Metric Spaces. In preparation, 2013.
  • S. L√§mmer, B. Gehlsen, and D. Helbing. Scaling laws in the spatial structure of urban road networks. Physica A, 363:89--95, 2006.
  • Lawler, Gregory F.; Schramm, Oded; Werner, Wendelin. Conformal invariance of planar loop-erased random walks and uniform spanning trees. Ann. Probab. 32 (2004), no. 1B, 939--995. MR2044671
  • Licea, Cristina; Newman, Charles M. Geodesics in two-dimensional first-passage percolation. Ann. Probab. 24 (1996), no. 1, 399--410. MR1387641
  • Penrose, Mathew. Random geometric graphs. Oxford Studies in Probability, 5. Oxford University Press, Oxford, 2003. xiv+330 pp. ISBN: 0-19-850626-0 MR1986198
  • Steele, J. Michael. Probability theory and combinatorial optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. viii+159 pp. ISBN: 0-89871-380-3 MR1422018
  • Stoyan, D.; Kendall, W. S.; Mecke, J. Stochastic geometry and its applications. With a foreword by D. G. Kendall. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons, Ltd., Chichester, 1987. 345 pp. ISBN: 0-471-90519-4 MR0895588
  • Wang, Jun; Provan, Gregory. Topological analysis of specific spatial complex networks. Adv. Complex Syst. 12 (2009), no. 1, 45--71. MR2510456
  • Wikipedia. A demonstration of Brownian scaling, 2010. http://en.wikipedia.org/wiki/File:Wiener_process_animated.gif [Online; accessed 14-May-2010].
  • Yukich, Joseph E. Probability theory of classical Euclidean optimization problems. Lecture Notes in Mathematics, 1675. Springer-Verlag, Berlin, 1998. x+152 pp. ISBN: 3-540-63666-8 MR1632875


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.