Spatial Networks

Marc Barthelemy

Source-linked AI summary

Spatial Networks

Marc Barthelemy

arXiv:1010.0302v2Oct 2, 2010cond-mat.stat-mechcond-mat.dis-nncs.SIphysics.soc-phq-bio.NC

TL;DR

Spatial networks require analysis that combines topology with node locations, distances, and edge costs because spatial constraints alter network structure and processes. This review synthesizes characterization tools, empirical observations, formation models, and processes on spatial networks, concluding that space produces recurring topology–traffic correlations while mobility patterns remain scale- and context-dependent.

Problem
Existing network reviews treated spatial aspects briefly despite their relevance to infrastructures, communication, biological systems, urbanism, and epidemiology.
Method
The paper reviews tools for characterizing spatial networks, empirical properties, formation models, and processes including mobility, resilience, and disease spread.
Results
Spatial constraints induce nonlinear correlations among topology, traffic, and distance, while mobility trip distributions vary with scale, population, congestion, and transportation mode.
Takeaways & Limitations
Spatial constraints favor regional hubs, locally reinforce preferential attachment, and can produce degree cutoffs, increased clustering, and lattice-like or small-world path-length behavior.
Takeaways & Limitations
The theoretical discussion assumes particular distance distributions, including uniformly distributed distances and a power-law trip-distance form.

Abstract

from arXiv · show

Complex systems are very often organized under the form of networks where nodes and edges are embedded in space. Transportation and mobility networks, Internet, mobile phone networks, power grids, social and contact networks, neural networks, are all examples where space is relevant and where topology alone does not contain all the information. Characterizing and understanding the structure and the evolution of spatial networks is thus crucial for many different fields ranging from urbanism to epidemiology. An important consequence of space on networks is that there is a cost associated to the length of edges which in turn has dramatic effects on the topological structure of these networks. We will expose thoroughly the current state of our understanding of how the spatial constraints affect the structure and properties of these networks. We will review the most recent empirical observations and the most important models of spatial networks. We will also discuss various processes which take place on these spatial networks, such as phase transitions, random walks, synchronization, navigation, resilience, and disease spread.

d. Betweenness centrality.

Betweenness centrality measures how nodes organize shortest-path flows, but spatial embedding shifts centrality from degree-driven hubness toward geographic position and can be reshaped by long links.

Betweenness centrality g(i) counts shortest paths between node pairs that pass through node i, measuring its importance for network flows.Terminal nodes have zero betweenness under this definition.
In a one-dimensional lattice, shortest paths concentrate near the barycenter, making central nodes spatially central rather than necessarily high-degree.For distant node pairs, paths are likely to pass near the network barycenter.
In purely topological networks, rewiring progressively weakens the correlation between centrality and position while strengthening its correlation with degree.Hubs become natural crossroads for paths, producing a correlation between degree and average betweenness.
For a one-dimensional lattice, g0(i) = (i −1)(N −i) peaks at i = N/2, so spatial location determines the baseline centrality profile.For N = 100, the maximum is at N/2 = 50.
Adding long links to a lattice creates centrality anomalies by reducing centrality along shortcut-spanned regions and increasing it at shortcut endpoints.This behavior represents deviations from the usual degree-centrality relation in spatially constrained networks.

a. Weight and spatial heterogeneity.

The North American airline network combines heavy-tailed connectivity with super-linear relationships between degree, traffic, and connection distance. Spatial structure also appears in clustering, betweenness fluctuations, community organization, and the need for models combining embedding, topology, and weights.

Weight and spatial heterogeneity: γ ≃2.0 with an exponential cut-off describes the airport degree distribution, reflecting physical constraints on maximum connections.The network is characterized as a spatial, non-planar small-world network with heterogeneous topology.
Weight and spatial heterogeneity: N = 935 vertices, ⟨k⟩≈8.4, and ⟨ℓ⟩≈4 characterize the North American network used for statistical analysis.The study focuses on one continental network to separate domestic and intercontinental distance scales.
Weight and spatial heterogeneity: βw ≃1.7 for weight strength and βd ≃1.4 for distance strength show that traffic and distance per connection increase super-linearly with degree.Larger airports have higher traffic and farther-reaching connections, linking topology with geography.
Betweenness Centrality: The North American network has high clustering and a slight disassortative trend at large degree, partly because regional data omit many intercontinental hub connections.The figure compares topological and weighted assortativity and clustering.
Betweenness Centrality: Betweenness centrality shows large fluctuations at fixed degree, so highly central airports can have relatively low degree and vice versa.This behavior motivates spatial network models that reproduce betweenness features while jointly representing embedding, topology, and weights.
Community detection: Modularity optimization identifies geographically organized airline communities and spatial anomalies, while inter-community links may matter for disease spread.The detected communities are visualized by assigning each airport a color.
Bus, subway, railway, and commuters: The Boston subway network has ⟨ℓ⟩∼16, exceeding ln 124 ≈5 and lying closer to a two-dimensional spatial-network expectation.The example uses a network of N = 124 stations.

a. Subways.

Subway and railway networks show strong spatial signatures: large path lengths, high clustering, and constrained degree distributions. Their structural indicators do not always predict operational load reliably.

Public transportation networks span 152–2811 nodes in one study and 1494–44629 in another, with station counts strongly correlated with population in the former.
Average shortest paths are large, around 10 or between 6.4 and 52.0, suggesting scaling closer to N^1/2 than logarithmic growth.
Average clustering ranges from 0.055 to 0.161 and exceeds Erdős–Rényi expectations by factors of 41–625.
The Indian railway network has ⟨ℓ⟩≈5, clustering above 0.7, an exponential degree distribution, and flat degree correlations.
Swiss railways have average degree ≈2.1, average shortest path ≈47, high clustering relative to random networks, and a peaked, exponentially decreasing degree distribution.
Betweenness correlates weakly with degree and real load, while degree predicts real load better than betweenness centrality in the EU rail analysis.The reported Pearson correlations are 0.5 for betweenness–degree and 0.26 for betweenness–real load.

c. Urban commuters network.

Urban movement networks connect locations through daily flows and exhibit heterogeneous traffic and degree-related structure. At small urban scales, spatial constraints may not dominate the observed topology.

The Portland network represents simulated movements of 1.6 million individuals among buildings, homes, and other locations.
Out-degree and out-traffic are well fitted by power laws, while clustering remains large across activity-specific subnetworks.
Aggregating all activities produces clustering that scales as 1/k, whereas work-activity clustering is almost constant.
The Sardinia interurban commuting network contains 375 municipalities and 1.6 million inhabitants, with peaked degrees and flow heterogeneity fitted by a power law of exponent ≈1.8.
Modularity-based communities in interurban commuting flows align with administrative regions, showing that community detection can reveal geographically meaningful organization.

4. Cargo-ship

Cargo-shipping networks combine broad connectivity, weighted traffic concentration, and geographic community structure. Their directional flows and motif patterns distinguish distribution networks while also revealing similarities across network types.

More than 90% of world trade is carried by sea, making cargo-ship networks especially important infrastructure networks.
The container-cargo dataset contains 878 ports, 1802 lines, and 7955 edges in its L-space representation.
Weighted clustering and assortativity exceed their unweighted counterparts, indicating that much traffic links hubs to other hubs.
Cargo-network betweenness increases with degree with few anomalies, possibly because geographical constraints are less severe for ships than for air travel.
The larger 2007 dataset has average shortest path ⟨ℓ⟩≈2.5, with over 50% of origin–destination pairs connected within two steps or fewer.
The weight distribution exponent is ≈1.7, and 59% of linked pairs exist in only one direction, reflecting strongly asymmetric flows.
Distribution networks can have asymmetric weights, unlike travel networks where round trips tend to produce wij≈wji.
Cargo fleets show geographically consistent communities and motif distributions surprisingly similar to those of Web and social networks.Community structure is reported for container ships, bulk dry carriers, and oil tankers; the similarity suggests possible superuniversal features.

a. Degrees, lengths, and cell areas.

Urban road networks display reproducible scaling in connectivity and total length, alongside broad cell-area and dual-degree distributions. These observations challenge simple regular-lattice models of street structure.

Street-segment lengths decrease rapidly in London, with a fitted exponent γ≃3.36 implying finite mean and dispersion.
The density-based argument reproduces the observed scaling of total network length with N and the prefactor μ≈⟨k⟩k/2.
Dresden road-network cell areas follow a power law with exponent α≃1.9, rather than concentrating around a regular-lattice value.
The proposed universal interpretation of the cell-area exponent relies on random density variation, but additional measurements are needed to test it.
Most cells have form factors between 0.3 and 0.6, indicating diverse shapes inconsistent with an almost regular lattice.
Dual road-network degree distributions in the US, England, and Denmark are broad and follow power laws with 2.0<γ<2.5.

b. Betweenness centrality.

Spatial constraints couple network topology to geometry, shaping centrality, efficiency, cost, and infrastructure structure. Empirical transportation and power-grid studies show heterogeneous centrality or load alongside spatially constrained degree and clustering patterns.

Betweenness centrality serves as a traffic proxy when flows between node pairs are assumed equal, revealing how network structure couples to spatial location.
Power-law betweenness distributions in German road networks have exponents from 1.279 to 1.486, with Dresden near 1.36.The broad distributions indicate strong traffic heterogeneity and a few highly central roads.
Small changes in the alpha index can produce large changes in shortest-path structure because efficiency varies more broadly than meshedness.Efficiency generally rises with cost but saturates near 0.8; doubling relative cost typically shifts efficiency from about 0.6 to 0.8.
Power-grid degree distributions are peaked and approximately exponential, while load has a broad distribution and 15% of edges are cut-edges.The cited studies concern Southern Californian and North American grids; clustering is relatively large and approximately independent of degree in the Western US grid.
Internet routers form a spatially distributed network whose link lengths decrease rapidly, while clustering behavior differs between router and aggregated AS levels.The review interprets these observations as competition between preferential attachment and spatial dependence, with node locations treated as model inputs.

4. Geography in social networks

Spatial proximity shapes social ties and communication patterns, but distance-decay estimates vary across studies. Mobile-phone evidence links distance with clustering and call duration, while travel studies identify regularities and competing explanations for trip-time distributions.

Mobile-phone data from 3.3 million Belgian customers show social-tie intensity decaying with distance, with an exponent of 2.0 over 1–100 kms.The review relates this exponent to a gravity law and Kleinberg’s navigability theorem.
Most friendships occur within users’ spatial neighborhoods, although studies disagree about the precise decay form and exponent.Short-distance links are reported across four online social networks, and spatial dependence also extends to collaboration.
For phone links, triangle membership decreases with distance and plateaus near 0.32 beyond 40 kms, while call duration saturates near 4 minutes.These observations motivate short-distance face-to-face and long-distance communication regimes with different clustering and durations.
Daily travel-time studies report an approximately constant average across UK transportation modes over 27 years, consistent with a travel-energy budget.The estimated average daily energy budget is about 615 kJ, with mode-specific energy consumption rates.
Rescaled individual travel times follow a universal distribution across transportation modes, with an energy term suppressing very short trips.The suppression is associated with the Simonson effect and selection of less costly modes for short journeys.

a. Mobile phone and GPS studies.

Mobile-phone, GPS, RFID, and origin-destination data reveal spatial regularities in human movement across national, urban, and inter-city scales. These studies report contrasting displacement distributions and gravity-law relationships whose parameters depend on measurement and spatial granularity.

National mobile-phone studies fit user displacements with a Levy law having β ≃ 1.75 and ∆r0 ≃ 1.5 km.The cutoff varies from about 400 kms to 80 kms between recording protocols, whose samples and observation schedules differ.
GPS data from Florence show exponentially distributed total daily trip lengths, apparently independent of road-network structure.The authors connect this pattern to Maxwell distributions and possible general principles governing human movement.
London Oyster-card trajectories reveal polycentric activity organization, broadly distributed traffic with exponent about 1.3, and peaked displacement lengths.The system provides instantaneous subway-flow information from RFID cards.
Gravity-law estimates depend on spatial granularity: Voronoi-based and county-based commuter studies can produce different results because administrative boundaries may not match mobility centers.This is identified as the modifiable areal unit problem.
For inter-city cargo movement, a truncated power-law deterrence function fits best with κ = 4,900 kms and σ = 0.59, but pairwise predictions remain dispersed.The observed-versus-predicted comparison has Kendall’s tau τ = 0.433.

e. Theoretical discussion.

The review derives gravity-law forms from entropy maximization and examines urban mobility scaling, while emphasizing unresolved cost functions and empirical heterogeneity.

Theoretical discussion: Entropy maximization derives the gravity model under origin-destination constraints and a total travel-cost constraint.Lagrange multipliers determine the trip matrix subject to these constraints.
Theoretical discussion: A logarithmic distance cost yields power-law trip decay, whereas a distance-proportional cost yields exponential decay.The exact dependence of travel cost on distance remains unresolved.
Urban mobility scaling: β ≃0.6 for 367 US cities, placing total vehicle miles between nearest-neighbor and random-trip mobility extremes.The result suggests a mixture of centralized and local trips, possibly reflecting polycentric organization.
Urban mobility scaling: β = 0.6 corresponds to τ = 1.8, indicating slow trip-volume decay with distance and trips across many length scales.An exponential distribution would instead produce τ > 2.
Open issues: Gravity-law results vary with transportation mode, spatial scale, trip type, user heterogeneity, and discretization.The review identifies these factors as possible sources of differing deterrence functions and exponents.
Neural networks: Brain-network evidence includes large clustering, but degree distributions remain debated and shortest-path estimates vary with network size.For networks of N ≈ 1,000–4,000, average shortest path length varies by a factor of about 1.7–1.8.

E. Summary: Existence of general features

Spatial embedding produces recurring structural signatures across networks, although their expression depends on planarity, topology, traffic, and measurement scope.

Network typology: Spatial networks divide broadly into planar networks and non-planar networks whose nodes occupy space while links incur length-related costs.Roads are examples of planar networks; airlines, cargo ships, and the Internet are non-planar examples.
Structural effects: Spatial constraints usually produce peaked degree distributions, especially in planar networks, while airline-like networks can retain broad distributions.The constraints restrict the appearance of large degrees.
Structural effects: Link-length distributions are peaked in planar roads and streets but can be broader in the Internet and airline networks.Spatial constraints generally limit link lengths, with strength varying across network types.
Structural effects: Spatial constraints flatten assortativity and increase clustering by limiting hub connections and favoring cliques among nearby nodes.Short-range links restrict hub-to-hub attachment, while proximity promotes local triangles.
Path lengths and models: Average shortest paths scale as N^1/2 in two-dimensional planar networks, as in regular lattices, before shortcuts modify this behavior.The reviewed models include geometric graphs, spatial random graphs, spatial small-worlds, spatial growth models, and cost-minimizing networks.
Topology, traffic, and centrality: Spatial embedding creates nonlinear topology-traffic correlations and large betweenness fluctuations at fixed degree.Regional hubs can have greater strength, while centrality also reflects spatial position and proximity to the network’s gravity center.
Mobility networks: Mobility distributions depend on scale, population, congestion, and transport mode, leaving a clear typology as an open problem.Urban trip lengths tend to be peaked, whereas larger-scale trip lengths can follow a broad law with exponent about 1.6.

1. The simplest random geometric graph

Random geometric graphs connect spatially nearby nodes and provide a tractable model for studying clustering, degree heterogeneity, and giant-component formation.

Definition and setup: Random geometric graphs connect points when a geometric proximity condition is satisfied, most simply when their separation is below a threshold.They are foundational models in spatial-network theory and continuum percolation.
Definition and setup: For fixed average degree, increasing the number of nodes requires shrinking the connection radius.The model represents nodes as spheres connected when their separation is less than twice their radius.
Percolation: The giant component appears above a critical average degree ⟨k⟩c = 1 + bd^-γ, with b = 11.78(5) and γ = 1.74(2).In infinite dimension, this scaling approaches the Erdős–Rényi threshold ⟨k⟩c = 1.
Degree distribution: Spatial density fluctuations can generate scale-free degree distributions even though uniform-density graphs have rapidly decaying degree distributions.If p(r) ∼ r^-β, the resulting degree distribution follows P(k) ∼ k^-d/β.
Clustering: Average clustering decreases from 3/4 in one dimension to values of order 10^-1 around dimension 10, independently of node count.Random geometric graphs are therefore much more clustered than Erdős–Rényi graphs, whose clustering scales as 1/N.
Applications: In ad-hoc networks, short-range communication can propagate information over longer distances through multihop routes and alternate paths.The model also permits distance-dependent connection probabilities and calculations of clustering and giant-component size.

2. Random geometric graph in hyperbolic space

Spatial network models show how geometry can generate heterogeneous, clustered, or small-world structures. Hyperbolic geometry yields scale-free networks, while distance-dependent links create transitions between large-world and small-world behavior.

Random geometric graph in hyperbolic space: The hyperbolic model assigns links using a distance threshold or connection probability based on hyperbolic distance.The hyperbolic distance is defined from the radial and angular coordinates of two nodes.
Random geometric graph in hyperbolic space: Hyperbolic random geometric graphs naturally produce scale-free degree distributions through hidden hyperbolic geometry.The power-law exponent depends on the ratio α/ζ, linking network heterogeneity to hyperbolicity and connection parameters.
Random geometric graph in hyperbolic space: These hyperbolic graphs also exhibit strong clustering, and one parameterization reproduces Internet measurements of degree, assortativity, and clustering.The reported parameters are α = 0.55, ζ = 1, and β = 2.
Scale-free networks on lattices: A lattice construction generates scale-free spatial networks by connecting each node to nearby neighbors until its assigned degree is reached.Larger assigned degrees produce larger connected-neighbor regions, while long links disrupt concentric chemical shells.
Scale-free networks on lattices: The lattice model retains the Euclidean fractal dimension while having a minimal length exponent dmin < 1 for d > 1.This combines Euclidean dimensional scaling with unusually short chemical distances.
Spatial generalizations: Distance-dependent shortcut models have a threshold αc = d+1 separating large-world scaling from small-world logarithmic behavior.For α > αc, links remain too short to change lattice-like behavior; for α < αc, a logarithmic regime emerges.

a. Finite range case.

Finite interaction ranges introduce a crossover between spatial and scale-free network behavior, while spatial costs reshape topology, traffic, centrality, and network efficiency. Models balancing distance against centrality or transport cost produce networks with characteristic trade-offs between construction cost, accessibility, and realism.

The interaction range r_c introduces a crossover: when it approaches system size, distance becomes irrelevant and the network is scale-free; when small, spatial properties emerge.
Spatial constraints limit available long-distance connections, suppress large degrees, increase clustering, and move the most central nodes closer to the network’s spatial barycenter.The clustering coefficient is expected to be large when distance effects are important, with longer links reducing clustering relative to the zero-constraint limit.
For N > N* the network is a small-world with ⟨ℓ⟩∼log N, whereas for small interaction ranges it behaves more like a lattice with ⟨ℓ⟩∼N^α.The spatial regime may still contain rare longer links, and the authors note that larger networks and better statistics are needed.
Increasing spatial constraints replaces global hubs with regional hubs, producing super-linear traffic-degree relations while total traffic remains directed toward those regional hubs.The mechanism is that long-distance links are less probable and can be established mainly toward system hubs.
The cost-centrality model interpolates between a star network at small λ and a Euclidean minimum spanning-tree-like network at large λ, with intermediate values yielding power-law degree distributions.The model minimizes E = λd_E(i, j) + h_j, balancing distance cost against node centrality.
q decreases sharply as α increases from zero while average edge length increases slowly, suggesting low-cost networks with good efficiency; empirical systems have l/l_MST in [1.12, 1.63] and route factor below 1.6.Compared with the MST, route factor improves by a factor in the range [1.4, 1.8].
These distribution-network models produce trees, simplifying real-world networks that usually contain loops, and they omit co-evolution between point density and network structure.The authors describe the model as a useful starting point despite these limitations.
Local optimization generates street patterns whose global properties agree with empirical data, but the distribution of nodes ρ(r) is crucial to the resulting network.The model can produce non-trivial global properties without a well-defined blueprint.

3. From the MST to the SPT

Spatial optimization interpolates between minimum-distance and shortest-path objectives, producing trees whose topology reflects trade-offs among edge length, centrality, traffic, and efficiency. These models also show that spatial constraints shape hierarchy, degree distributions, synchronization, and loop formation.

From the MST to the SPT: The generalized energy combines Euclidean link cost and betweenness centrality, with µ and ν controlling the relative weight of distance and topology.Its minimization provides an interpolation between the minimum spanning tree and shortest path tree.
From the MST to the SPT: Different parameter choices produce a minimum spanning tree, an optimal traffic tree with local hubs, or a minimum Euclidean distance tree.For (µ, ν) = (0, 1), total distance is minimized; for (1/2, 1/2), centralization and minimum distance interact; for (1, 1), centrality dominates.
From the MST to the SPT: Optimal traffic trees exhibit hierarchical spatial organization, with long links connecting regional hubs that dispatch traffic to smaller hubs.The same optimization can generate degree–traffic correlations and superlinear strength–degree behavior.
From the MST to the SPT: Spatial constraints generally prevent broad degree distributions in optimized trees, although another optimization model produced a degree power law with exponent −2 for a network of size N = 100.The authors describe this as evidence that optimization might help explain scale-free features, while noting that larger-network statistics are needed for confirmation.
From the MST to the SPT: Increasing connection cost changes networks from minimal-length structures toward fewer hubs and longer spokes, while intermediate cost–efficiency trade-offs can produce modular organization.In the communication model, λ = 0 gives a complete graph and λ = 1 gives a minimum spanning tree.
Beyond trees: noise and loops: Fluctuations and resilience to damage are proposed as reasons natural optimal networks can contain loops rather than being trees.The cited studies report loop formation resembling patterns observed in real leaves and identify quantitative loop conditions as an open question.

F. Summary: Effect of space on networks

Embedding networks in space alters topology, centrality, traffic correlations, and dynamical behavior because connection costs constrain which links are feasible. The review synthesizes empirical patterns, spatial network models, and processes including diffusion, synchronization, navigation, and phase transitions.

Effect of space on networks: Spatial constraints limit connections to hubs, increase local clustering, and produce larger average shortest paths through geographically local connectivity.They also impose a degree-distribution cutoff dependent on node density and yield nearly flat assortativity.
Effect of space on networks: Spatial embedding creates large betweenness fluctuations because centrality reflects both node degree and proximity to the barycenter.This allows less-connected nodes near the spatial center to carry many paths.
Effect of space on networks: Spatial constraints generate nonlinear topology–traffic correlations by favoring regional hubs and restricting reinforcing links to hubs.The resulting distance–strength relation has an exponent β_d > 1.
Space and optimal networks: In optimized traffic networks, long-range links carry large traffic and connect regional hubs that distribute flow across smaller regions.This links spatial efficiency with hub-and-spoke organization and strong distance–traffic correlations.
Diffusion on spatial networks: For diffusion on one-dimensional power-law small-world networks, α = 2 separates recurrent behavior for α ≥ 2 from transient behavior for α < 2.Below the crossover, long shortcuts qualitatively alter lattice behavior; at later times walkers recover Erdős–Rényi-like stretched-exponential decay.
Navigation: Kleinberg’s decentralized greedy search reaches targets in logarithmic time when the shortcut exponent matches dimension, α = d; other exponents scale faster.The search forwards messages to the geographically closest neighbor, using only local geographical information.

2. Sketch of Kleinberg’s proof

Kleinberg’s proof analyzes decentralized navigation by partitioning the spatial lattice into distance phases and estimating the chance that a long-range link exits each phase. The resulting bounds explain why α = d is optimal and why other exponents require polynomially many steps.

2. Sketch of Kleinberg’s proof: At α = 2, the long-range-link probability scales as P(u → v) ∼ 1/(ln N)d_E(u,v)^2, and nodes are grouped into logarithmically many distance phases.The phase index records the message’s lattice distance from the target.
2. Sketch of Kleinberg’s proof: The probability of leaving a phase through a long-range link is bounded below by 1/(136 ln N), giving an average phase exit time of order ln N.The proof then combines the phase exit times to obtain the decentralized delivery-time bound.
2. Sketch of Kleinberg’s proof: For α = 2, the decentralized algorithm achieves the minimum time, logarithmic in N, among the analyzed spatial shortcut distributions.The same condition generalizes to α = d in d dimensions.
2. Sketch of Kleinberg’s proof: For α < 2, assuming T ∼ N^δ, the final long-range jump must enter a target-centered region whose size scales as pN^δ.The probability constraints yield the minimum exponent δ, with the d-dimensional expression δ_min = (d − α)/(d + 1).
2. Sketch of Kleinberg’s proof: For α > 2, mostly short links require a long-jump event during T ∼ N^β, while covering distance N imposes β + γ = 1.Combining these constraints recovers the β_min bound shown in the phase diagram.
3. Searching in spatial scale-free networks: In spatial scale-free networks, degree-aware algorithms find paths at most one hop longer than the average shortest path using only local information.Their success is attributed to hubs, whereas greedy search can sometimes become trapped in loops.

4. Navigability and metric space

Spatial structure affects navigability, percolation, network resilience, and disease spread. Clustering, degree structure, shortcuts, metric information, and interdependence determine whether processes remain efficient or undergo abrupt transitions.

Navigability and metric space: Smaller γ and larger α reduce average shortest paths, while strong clustering increases successful greedy-routing paths.The review links this to fast routing through hubs and efficient local search from clustering.
Navigability and metric space: Real-world communication, transportation, social, and biological networks lie in the navigable region of the clustering–degree-distribution exponent plane.In the non-navigable region, greedy-routing efficiency decreases with system size.
Navigability and metric space: Geographic information enables global routing for 13% of source–target pairs in a blogger social network, with rank-based distance accounting for population density.Under uniform two-dimensional density, rank scales with distance and recovers the Kleinberg condition α = d.
Percolation and small-worlds: Shortcuts drive mean-field percolation behavior, introduce a shortcut length scale ξSW ∼1/p^(1/d), and lower the percolation threshold as their density increases.The resulting exponents include τ = 3/2 and σ = 1, and the Watts–Strogatz model resembles a random graph in infinite dimension.
Failure of interdependent networks: Interdependent power and Internet networks can exhibit lower critical thresholds and abrupt first-order collapse of the giant component.Dependence between hubs and small-degree nodes further increases system vulnerability.