Spatial network

A random geometric graph, one of the simplest models of spatial network.

A spatial network (sometimes also geometric graph) is a graph in which the vertices or edges are spatial elements associated with geometric objects, i.e., the nodes are located in a space equipped with a certain metric. The simplest mathematical realization of spatial network is a lattice or a random geometric graph, where nodes are distributed uniformly at random over a two-dimensional plane; a pair of nodes are connected if the Euclidean distance is smaller than a given neighborhood radius. Transportation and mobility networks, Internet, mobile phone networks, power grids, social and contact networks and biological neural networks are all examples where the underlying space is relevant and where the graph's topology alone does not contain all the information. Characterizing and understanding the structure, resilience and the evolution of spatial networks is crucial for many different fields ranging from urbanism to epidemiology.

Examples

An urban spatial network can be constructed by abstracting intersections as nodes and streets as links, which is referred to as a transportation network. Beijing traffic was studied as a dynamic network and its percolation properties have been found useful to identify systematic bottlenecks.

One might think of the 'space map' as being the negative image of the standard map, with the open space cut out of the background buildings or walls.

Characterizing spatial networks

The following aspects are some of the characteristics to examine a spatial network:

• Planar networks

In many applications, such as railways, roads, and other transportation networks, the network is assumed to be planar. Planar networks build up an important group out of the spatial networks, but not all spatial networks are planar. Indeed, the airline passenger networks is a non-planar example: Many large airports in the world are connected through direct flights.

• The way it is embedded in space

There are examples of networks, which seem to be not "directly" embedded in space. Social networks for instance connect individuals through friendship relations. But in this case, space intervenes in the fact that the connection probability between two individuals usually decreases with the distance between them.

• Voronoi tessellation

A spatial network can be represented by a Voronoi diagram, which is a way of dividing space into a number of regions. The dual graph for a Voronoi diagram corresponds to the Delaunay triangulation for the same set of points. Voronoi tessellations are interesting for spatial networks in the sense that they provide a natural representation model to which one can compare a real world network.

• Mixing space and topology

Fig. 1. Lattice network in two dimensions. The balls are the nodes and the edges connecting neighboring nodes are the links.

Fig. 2. Spatially interdependent lattice networks. Two square lattices A and B, where in each lattice a node has two types of links: connectivity links in the same layer and dependency links between the layers. Every node is connected (with connectivity links) to its four nearest neighbors within the same lattice and a fraction of nodes in each network have dependency links to the other network. If a node fail in one network its dependent node in the other network will also fail, even if it is still connected to its network via connectivity links.

Examining the topology of the nodes and edges itself is another way to characterize networks. The distribution of degree of the nodes is often considered, regarding the structure of edges it is useful to find the Minimum spanning tree, or the generalization, the Steiner tree and the relative neighborhood graph.

Fig. 3: Spatially embedded multiplex networks. The nodes occupy regular locations in two-dimensional lattice while the links in each layer (blue and green) have lengths that are exponentially distributed with characteristic length ζ = 3 and are connected at random with degree k=4.

Lattice networks

Lattice networks (see Fig. 1) are useful models for spatial embedded networks. Many physical phenomenas have been studied on these structures. Examples include Ising model for spontaneous magnetization, diffusion phenomena modeled as random walks and percolation. Recently to model the resilience of interdependent infrastructures which are spatially embedded a model of interdependent lattice networks was introduced (see Fig. 2) and analyzed . A spatial multiplex model was introduced by Danziger et al and was analyzed further by Vaknin et al. For the model see Fig. 3. It was shown that localized attacks on these two last models (shown in Figs. 2 and 3) above a critical radius will lead to cascading failures and system collapse. Percolation in a single 2d layer structure (like Fig. 3) of links having characteristic length $\zeta$ have been found to have a very rich behavior. In particular, the behavior up to linear scales of $\zeta ^{3/2}$ is like in high dimensional systems (mean field) at the critical percolation threshold. Above $\zeta ^{3/2}$ the system behaves like a regular 2d system.

Spatial modular networks

File:The giant component.png

Figure 4. (a) The giant component P∞ as a function of p for different values of ζ on semi log scale with K = 4 and Q = 10. ${p}_{\text{c}}^{\text{spatial}}$ depends only on Q (equation (4)). The inset shows finite size effect in the $p{< }{p}_{\text{c}}^{\text{ER}}\left(=0.25\right)$ regime. Indeed, as N increases P∞ goes to zero (N = 106, 107, 108—red, green and blue respectively) in this regime. (b) ${p}_{\text{c}}^{\text{spatial}}$ as a function of 1/(kinter + K) for K = 4 and large values of kinter for different values of ζ. For large values of ζ the network is similar to ER networks and therefor ${p}_{\text{c}}^{\text{spatial}}=1/\left({k}_{\text{inter}}+K\right)$. Here L = 104.

Many real-world infrastructure networks are spatially embedded and their links have characteristics length such as pipelines, power lines or ground transportation lines are not homogeneous, like in Fig. 3, but rather heterogeneous. For example, density of links within cities are significantly higher than between cities. Gross et al. developed and studied a similar realistic heterogeneous spatial modular model using percolation theory in order to better understand the effect of heterogeneity on such networks. The model assumes that inside a city there are many lines connecting different locations, while long lines between the cities are sparse and usually directly connecting only a few nearest neighbors cities in a two dimensional plane, see Fig. 4. It is found that this heterogeneous model experiences two distinct percolation transitions, one when the cities disconnect from each other and the second when each city breaks apart. This is in contrast to the homogeneous model, Fig. 3 where a single transition is found.

Probability and spatial networks

In the "real" world many aspects of networks are not deterministic - randomness plays an important role. For example, new links, representing friendships, in social networks are in a certain manner random. Modelling spatial networks in respect of stochastic operations is consequent. In many cases the spatial Poisson process is used to approximate data sets of processes on spatial networks. Other stochastic aspects of interest are:

• The Poisson line process
• Stochastic geometry: the Erdős–Rényi graph
• Percolation theory

Approach from the theory of space syntax

Another definition of spatial network derives from the theory of space syntax. It can be notoriously difficult to decide what a spatial element should be in complex spaces involving large open areas or many interconnected paths. The originators of space syntax, Bill Hillier and Julienne Hanson use axial lines and convex spaces as the spatial elements. Loosely, an axial line is the 'longest line of sight and access' through open space, and a convex space the 'maximal convex polygon' that can be drawn in open space. Each of these elements is defined by the geometry of the local boundary in different regions of the space map. Decomposition of a space map into a complete set of intersecting axial lines or overlapping convex spaces produces the axial map or overlapping convex map respectively. Algorithmic definitions of these maps exist, and this allows the mapping from an arbitrary shaped space map to a network amenable to graph mathematics to be carried out in a relatively well defined manner. Axial maps are used to analyse urban networks, where the system generally comprises linear segments, whereas convex maps are more often used to analyse building plans where space patterns are often more convexly articulated, however both convex and axial maps may be used in either situation.

Currently, there is a move within the space syntax community to integrate better with geographic information systems (GIS), and much of the software they produce interlinks with commercially available GIS systems.

History

While networks and graphs were already for a long time the subject of many studies in mathematics, physics, mathematical sociology, computer science, spatial networks have been also studied intensively during the 1970s in quantitative geography. Objects of studies in geography are inter alia locations, activities and flows of individuals, but also networks evolving in time and space. Most of the important problems such as the location of nodes of a network, the evolution of transportation networks and their interaction with population and activity density are addressed in these earlier studies. On the other side, many important points still remain unclear, partly because at that time datasets of large networks and larger computer capabilities were lacking. Recently, spatial networks have been the subject of studies in Statistics, to connect probabilities and stochastic processes with networks in the real world.

See also

• Hyperbolic geometric graph
• Spatial network analysis software
• Cascading failure
• Complex network
• Planar graphs
• Percolation theory
• Modularity (networks)
• Random graphs
• Topological graph theory
• Small-world network
• Chemical graph
• Interdependent networks

References

• Bandelt, Hans-Jürgen; Chepoi, Victor (2008). "Metric graph theory and geometry: a survey" (PDF). Contemp. Math. Contemporary Mathematics. 453: 49–86. doi:10.1090/conm/453/08795. ISBN 9780821842393. Archived from the original (PDF) on 2006-11-25.
• Pach, János; et al. (2004). Towards a Theory of Geometric Graphs. Contemporary Mathematics, no. 342, American Mathematical Society.

• Pisanski, Tomaž; Randić, Milan (2000). "Bridges between geometry and graph theory". In Gorini, C. A. (ed.). Geometry at Work: Papers in Applied Geometry. Washington, DC: Mathematical Association of America. pp. 174–194. Archived from the original on 2007-09-27.