The spatial structure of networks

By Michael T. Gastner, Mark Newman. 2004

453 citations recorded by the source corpus.

Abstract. We study networks that connect points in geographic space, such as transportation networks and the Internet. We find that there are strong signatures in these networks of topography and use patterns, giving the networks shapes that are quite distinct from one another and from non-geographic networks. We offer an explanation of these differences in terms of the costs and benefits of transportation and communication, and give a simple model based on the Monte Carlo optimization of these costs and benefits that reproduces well the qualitative features of the networks studied.

Subfields: Information Systems, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/c6b1c36f7aaec0bc22a718af71edca5d692c2c8b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

An efficient and principled method for detecting communities in networks (2011, background): “…as here, the vertices have well-deﬁned positions in geographic space, are often found to have higher probability of connection for vertex pairs located closer together [26, 27], which suggests that communities, if they exist, should be regional, consisting principally of blocks of nearby vertices.”
Spatial Networks (2010, unknown): “figure illustrates the expected behavior when the connection cost increases (similar results were obtained with the same model in [136]): for δ = 0, the connection cost is zero, only distance counts and the resulting network is essentially a minimal length network, such as a planar network of roads ”
Modeling population connectivity by ocean currents, a graph-theoretic approach for marine conservation (2007, background): “lighted in the terrestrial literature (Cantwell and Forman 1993; Urban and Keitt 2001; Calabrese and Fagan 2004; Gastner and Newman 2006; Proulx et al. 2005).”
Layered complex networks. (2005, methodology): “The graphs based on the physical infrastructure of such networks were analyzed on the examples of a power grid [5, 6], railway network [7], road networks [8, 9], or urban mass transportation systems [10, 11, 12, 13].”
Uncovering space-independent communities in spatial networks (2010, background): “In either case, space plays a crucial role by aﬀecting, directly or indirectly, network connectivity and making its architecture radically diﬀerent from that of random networks [3].”
Analyzing and modeling real-world phenomena with complex networks: a survey of applications (2007, methodology): “the distance, and it was used in [18, 292].”
Characterization of complex networks: A survey of measurements (2005, background): “y networks or the Internet, for example, where the position of cities and routers can be localized in a map and the edges between correspond to real physical entities, such as roads and optical ﬁbers [58]. This kind of networks is called geographical or spatial networks. Other important examples of ”
Link Prediction in Complex Networks: A Survey (2010, background): “It is known to be relevant to the existence of an airline, and the number of airlines decays with the increasing of corresponding distance [59,145].”
Changes in Transport and Non Transport Costs: Local vs. Global Impacts in a Spatial Network (2007, unknown): “…spatial network (M, E) is locally a tree at (i, j), and letM0(i,j) denote the subset of neighdesign outcome of economic problems in which total transport costs are minimized when agents care not only about distance but also about the number of nodes they have to cross (Gastner and Newman, 2004).”
A Graph‐Theory Framework for Evaluating Landscape Connectivity and Conservation Planning (2008, background): “Network topology is especially interesting because it is an emergent property that affects qualities such as spread of information and disease, vulnerability to disturbance, and stability (Albert & Barabasi 2002; Melian & Bascompte 2002; Gastner & Newman 2006).”
Geographic routing in social networks (2005, background): “(The proportion of links in a network that are between two entities separated by a particular geographic distance has been studied in a number of different contexts: the infrastructure of the Internet [14, 15, 37], small-scale email networks within a company [3, 4], transportation networks [14], and”
Complex network approaches to nonlinear time series analysis (2019, background): “This approach allows to connect the problem of choice of recurrence threshold to insights from the theory of random geometric graphs [150,170,171] and, more generally, spatial networks [68,69,172] on the percolation threshold εc or the more frequently studied critical mean degree zc(εc) in random ge”