![Random geometric graph](https://upload.wikimedia.org/wikipedia/commons/6/66/Random_geometric_graph.svg)
A spatial network (sometimes also
geometric graph) is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
in which the
vertices or
edges are ''spatial elements'' associated with
geometric
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...
objects, i.e., the nodes are located in a space equipped with a certain
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
.
[M. Barthelemy, "Morphogenesis of Spatial Networks", Springer (2018).] The simplest mathematical realization of spatial network is a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
or a
random geometric graph
In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing ''N'' nodes in some metric space (according to a specified probability distribution) and con ...
(see figure in the right), where nodes are distributed uniformly at random over a two-dimensional plane; a pair of nodes are connected if the
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
is smaller than a given neighborhood radius.
Transportation and mobility networks,
Internet
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
,
mobile phone networks,
power grids,
social and contact networks and
biological neural networks
A neural circuit is a population of neurons interconnected by synapses to carry out a specific function when activated. Neural circuits interconnect to one another to form large scale brain networks.
Biological neural networks have inspired t ...
are all examples where the underlying space is relevant and where the graph's
topology
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
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.
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.
[Hillier B, Hanson J, 1984, The social logic of space (Cambridge University Press, Cambridge, UK).]
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 is an adjective meaning "relating to a plane (geometry)".
Planar may also refer to:
Science and technology
* Planar (computer graphics), computer graphics pixel information from several bitplanes
* Planar (transmission line technologies), ...
. 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
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
, which is a way of dividing space into a number of regions. The dual graph for a Voronoi diagram corresponds to the
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
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
Examining the topology of the nodes and edges itself is another way to characterize networks. The distribution of
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
of the nodes is often considered, regarding the structure of edges it is useful to find the
Minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
, or the generalization, the
Steiner tree
In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a n ...
and the
relative neighborhood graph
In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to ...
.
Probability and spatial networks
In "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
In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of one ...
is used to approximate data sets of processes on spatial networks. Other stochastic aspects of interest are:
* The
Poisson line process
Poisson may refer to:
People
*Siméon Denis Poisson, French mathematician
Places
*Poissons, a commune of Haute-Marne, France
*Poisson, Saône-et-Loire, a commune of Saône-et-Loire, France
Other uses
*Poisson (surname), a French surname
*Poisson ...
* Stochastic geometry: the
Erdős–Rényi graph
*
Percolation theory
In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected ...
Approach from the theory of space syntax
Another definition of spatial network derives from the theory of
space syntax
The term space syntax encompasses a set of theories and techniques for the analysis of spatial configurations. It was conceived by Bill Hillier, Julienne Hanson, and colleagues at The Bartlett, University College London in the late 1970s to ea ...
. 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 line
Axial may refer to:
* one of the anatomical directions describing relationships in an animal body
* In geometry:
:* a geometric term of location
:* an axis of rotation
* In chemistry, referring to an axial bond
* a type of modal frame, in music ...
s 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 network
, also referred to as , is one of the Japan Railways Group (JR Group) companies and operates in western Honshu. It has its headquarters in Kita-ku, Osaka. It is listed in the Tokyo Stock Exchange, is a constituent of the TOPIX Large70 index, and ...
s, 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 system
A geographic information system (GIS) is a type of database containing Geographic data and information, geographic data (that is, descriptions of phenomena for which location is relevant), combined with Geographic information system software, sof ...
s (GIS), and much of the
software
Software is a set of computer programs and associated documentation and data. This is in contrast to hardware, from which the system is built and which actually performs the work.
At the lowest programming level, executable code consists ...
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
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, physics, mathematical sociology,
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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.
[P. Haggett and R.J. Chorley. ''Network analysis in geog-
raphy''. Edward Arnold, London, 1969.] 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
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
, to connect probabilities and stochastic processes with networks in the real world.
See also
*
Hyperbolic geometric graph
*
Spatial network analysis software
Spatial network analysis software packages are analytic software used to prepare graph-based analysis of spatial networks. They stem from research fields in transportation, architecture, and urban planning. The earliest examples of such software in ...
*
Cascading failure
A cascading failure is a failure in a system of interconnected parts in which the failure of one or few parts leads to the failure of other parts, growing progressively as a result of positive feedback. This can occur when a single part fails, i ...
*
Complex network
In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real s ...
*
Planar graphs
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
*
Percolation theory
In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected ...
*
Modularity (networks)
Modularity is a measure of the structure of networks or graphs which measures the strength of division of a network into modules (also called groups, clusters or communities). Networks with high modularity have dense connections between the nod ...
*
Random graphs
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs li ...
*
Topological graph theory
In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs.
Embedding a graph in ...
*
Small-world network
A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a sm ...
*
Chemical graph
In chemical graph theory and in mathematical chemistry, a molecular graph or chemical graph is a representation of the structural formula of a chemical compound in terms of graph theory. A chemical graph is a labeled graph whose vertices corres ...
*
Interdependent networks
The study of interdependent networks is a subfield of network science dealing with phenomena caused by the interactions between complex networks. Though there may be a wide variety of interactions between networks, ''dependency'' focuses on the ...
References
*
*
*
{{DEFAULTSORT:Spatial Network
*
Architectural theory
Environmental design
Environmental psychology
Application-specific graphs
Graph theory