BackgroundSIRSNsBackgroundSIRSNsScale-invariant random spatial networksDavid AldousSeptember 8, 2010David Aldous Scale-invariant random spatial networksBackgroundSIRSNsActual content is math theory: inventing and studying a (slightly) newclass of random process, an abstraction of road networks.Axiomatic setupMath examples – particular processes within the class.Consequences – properties of such processes.Realism?Framing the topic:How does your car GPS device find routes?Online road maps/routes differ from paper maps in 2 ways thatinfluence the way we set up the model.(end of talk) reflections upon data vs specific models vs. classes ofprocess.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsHow your car GPS device finds routesYou type street address (≈ 100 million in U.S.).Recognized as between two street intersections.U.S road network represented as a graph on about 15 million streetintersections (vertices).Want to compute the shortest route between two vertices. Neither of thefollowing two extremes is practical.pre-compute and store the routes for all possible pairs;or use a classical Dijkstra-style algorithm for a given pair withoutany preprocessing.Key idea: there is a set of about 10,000 intersections (transit nodes)with the property that, unless the start and destination points are close,the shortest route goes via some transit node near the start and sometransit node near the destination.[ Bast - Funke - Sanders - Schultes (2007); Science paper and patent]Given such a set, one can pre-compute shortest routes and route-lengthsbetween each pair of transit nodes; then answer a query by using theclassical algorithm to calculate the route lengths from starting (and fromdestination) point to each nearby transit node, and finally minimizingover pairs of such transit nodes. Takes 0.1 sec.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsCould regard this key fact (10,000 transit nodes such that . . . . . . ) asmerely an empirical property of real network. And in some qualitativesense it’s obvious – there’s a hierarchy of roads from freeways to dirttracks, and “transit nodes” are intersections of major roads.Is there some Theory? How do transit nodes arise in a math model?Why 10,000 instead of 1,000 or 100,000?Abraham - Fiat - Goldberg - Werneck (SODA 2010) define highwaydimension as the smallest integer h such that for every r and every ballof radius 4r, there exists a set of h vertices such that every shortest routeof length > r within the ball passes through some vertex in the set.They analyse algorithms exploiting transit nodes and other structure,giving performance bounds involving h and number of vertices andnetwork diameter.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsWhat kind of mathematical object should we model a roadnetwork as? Traditional paper maps suggest two possibilities. First, forintercity road networks.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsSecond, a “street map” showing every road within a town.http://creativecommons.org/licenses/by-sa/2.0/ http://openstreetmap.orgLicensed under the Creative Commons Attribution-Share Alike 2.0 license by the OpenStreetMap project and its contributors.OpenStreetMap http://www.openstreetmap.org/index.html1 of 1 9/7/10 10:22 AMDavid Aldous Scale-invariant random spatial networksBackgroundSIRSNsBen Fryhttp://benfry.com/allstreets/(fun aside): every road in the U.S.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsConceptual point: Online road maps/routes differ from paper maps in2 [obvious] ways that will motivate our modeling.Can zoom in – see greater detail in window covering less area.Can get routes between any two specified addresses.PrintRoute: 849.6 mi, 12 hr 22 minThis was your map view in the browser window.A: 1 Microsoft Way, Redmond, WA 98052-8300B: 1600 Amphitheatre Pkwy, Mountain View, CA 94043-1351Print - Maps http://www.bing.com/maps/print.aspx?mkt=en-us&z=6&s=r&c...1 of 2 6/9/10 11:05 AMDavid Aldous Scale-invariant random spatial networksBackgroundSIRSNsIdea behind our set-up: start with routes instead of roads.We abstract Google maps as an “oracle” that for any start/desinationpair (z1, z2) in the plane gives us a route r(z1, z2).Analogous to ergodic theory regarding the Hamlet text as one realizationfrom a stationary source, we regard Bing maps as containing onerealization of a “continuum random spatial network”. We will axiomatizethis object by axiomatizing properties of random routes R(z1, z2).The key assumption is scale-invariance, described intuitively as follows.David Aldous Scale-invariant random spatial networksBackgroundSIRSNs7 points in a window.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsScale-invariance means: doing this within a randomly positionedwindow, the statistics of the subnetwork observed don’t depend on thescale, i.e. don’t depend on whether the side length is 5 miles or 100 miles.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsWiener_process_animated.gif (GIF Image, 500x100 pixels) http://upload.wikimedia.org/wikipedia/commons/2/2a/Wiener_p...1 of 1 6/9/10 11:12 AMComments re scale-invariance:Wikipedia has nice “zoom in” animation for Brownianscale-invariance.For any real-world phenomena one might model by BM, there issome “bottom level”, some microscopic scale at which the BMmodel breaks down.Visualize animation of zooming into a particular model in our S-IclassTo have a network model which is exactly scale-invariant, we need towork in the continuum.Naive Euclidean scaling, not “scaling exponent”.David Aldous Scale-invariant random spatial networksBackgroundSIRSNsThoughts from a well-known mathematician 120 years ago.“What do you consider the largest map that would be really useful?”“About six inches to the mile.”“Only six inches!” exclaimed Mein Herr. “We very soon got to six yardsto the mile. Then we tried a hundred yards to the mile. And then camethe grandest idea of all! We actually made a map of the country, on thescale of a mile to the mile!”“Have you used it much?” I enquired.“It has never been spread out, yet,” said Mein Herr: “The farmersobjected: they said it would cover the whole country, and shut out thesunlight! So we now use the country itself, as its own map, and I assureyou it does nearly as well.”Sylvie and Bruno Concluded. Lewis Carroll (1889)David