INAUGURAL ARTICLE by a Recently Elected Academy Member:True scale-invariant random spatial networks

Some aspects of real-world road networks seem to have an approximate scale invariance property, motivating study of mathematical models of random networks whose distributions are exactly invariant under Euclidean scaling. This requires working in the continuum plane, so making a precise definition is not trivial. 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. One concrete model, based on minimum-time routes in a binary hierarchy of roads with different speed limits, has been shown to satisfy the axioms, and two other constructions (based on Poisson line processes and on dynamic proximity graphs) are expected also to do so. We initiate study of structure theory and summary statistics for general processes in the class. Many questions arise in this setting via analogies with diverse existing topics, from geodesics in first-passage percolation to transit node-based route-finding algorithms.We introduce and study a mathematical structure inspired by road networks. Although not intended as literally realistic, we do believe it raises and illustrates several interesting conceptual points and potential connections with other fields, summarized in the final section. Details will appear in a long technical paper (1). Here, we seek to explain in words rather than mathematical symbols.Consider two differences between traditional paper maps and modern online maps for roads, which will motivate two conceptual features of our model. On paper, one needs different maps for different scales—for the intercity network and for the street network in one town. The usual simplified mathematical models involve different mathematical objects at the two scales, for instance representing cities as points for an intercity network model (2). Online maps allow you to “zoom in” so that the window you see covers less real-world area but shows more detail, specifically (for our purpose) showing comparatively minor roads that are not shown when you “zoom out” again. As a first conceptual feature, we seek a mathematical model that represents roads consistently over all scales. Next, a paper map shows roads, and the user then chooses a “route” between start and destination. In contrast, a typical use of an online map is to enter the start and destination address and receive a suggested route. As a second conceptual feature, our model will treat routes as the basic objects. That is, somewhat paradoxically, in our model routes determine roads.Returning to the image of zooming in and out, the key assumption in our models is that statistical features of what we see in the map inside a window do not depend on the real-world width of the region being shown—on whether it is 5 miles or 500 miles. We call this property “scale invariance,” in accord with the usual meaning of that phrase within physics. Of course, our phrase “what we see” is very vague; we mean quantifiable aspects of the road network, and this is best understood via examples of quantifiable aspects described in the following section, and then the mathematical definition in the subsequent section. Note that scale invariance is not “scale-free network,” a phrase that has become attached (3) to the quite different notion of a (usually nonspatial) network in which the proportion of vertices with i edges scales for large i as for some γ. Our title reads “true scale invariance” to emphasize the distinction.More precisely, the property is “statistical” scale invariance, and two analogies with classical subjects may be helpful. Modeling English text as “random” seems ridiculous at first sight—authors are not monkeys on typewriters. However, the Shannon theory of “information” (4) (better described as “data compression”) does assume randomness in a certain sense, called “stationarity” or “translation invariance.” Roughly, the assumption is that the frequency of any particular word such as “the” does not vary in different parts of a text. Such an assumption is intuitively plausible and is very different from any sort of explicit dice-throwing model of pure randomness. Analogously, roads are designed rather than arising from some explicit random mechanism, but this does not contradict the possibility that statistical properties of road networks are similar in different locations and on different scales. So, just as information theory imagines the actual text of Pride and Prejudice as if it were a realization from some translation-invariant random process, we will imagine the actual road network of the United States as if it were a realization from some random process with certain invariance properties.A second analogy is with the “Wiener process,” a mathematical model in topics as diverse as physical Brownian motion, stock prices, and heavily-loaded queues. The mathematical model is exactly scale invariant (as explained and illustrated in a dynamic simulation in ref. 5) even though the real-world entities it models cannot be scale invariant at very small scales. Analogously, the exact scale invariance of our models is unrealistic at very small scales—we do not really have an arbitrarily dense collection of arbitrarily minor roads—but this is not an obstacle to interpreting the models over realistic distances.