PaperlayerView exact revision on arXiv

Source-linked AI summary

The structure and function of complex networks

M. E. J. Newman

arXiv:cond-mat/0303516v1cond-mat.stat-mechcond-mat.dis-nn

TL;DR

Large network research needs statistical descriptions because networks too large for meaningful visual inspection. This review synthesizes measures, models, and dynamical processes, while noting that predicting behavior from structure remains less developed.

  • Problem

    Large networks cannot be understood reliably by inspecting individual graphs, motivating statistical approaches to characterize their structure and behavior.

    Source: §I · p. 2

  • Method

    The review covers structural measures, network models, growth and preferential attachment, resilience, search, and dynamical processes on networks.

    Source: §I · p. 2, B. The model of Barab´asi and Albert · p. 32, A. Percolation theory and network… · p. 40

  • Results

    The field has made an excellent start on characterizing and modeling network structure, while studies of how structure affects system behavior remain in their infancy.

    Source: §I · p. 2

  • Takeaways & Limitations

    Network theory aims to connect measured structural properties and local vertex rules to the behavior of networked systems.

    Source: §I · p. 2

Abstract

from arXiv · show

Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.

A. The small-world effect

This section surveys the small-world effect and related structural properties across information, technological, biological, and random networks. It examines short paths, clustering, degree distributions, degree correlations, scale-free behavior, and how network size and tail fluctuations affect maximum-degree estimates.

B. Information networks

  • Information networks include citation networks and the cyclic World Wide Web, whose observed structure is affected by hyperlink-crawl bias toward pages with more incoming links.Citation networks are acyclic and can include uncited papers, whereas Web crawls may underestimate the fraction of pages with low in-degree.Source: Figure 4 · p. 7, B. Information networks · p. 7

C. Technological networks

  • Technological networks distribute commodities or information, including power grids, transportation systems, roads, railways, and the physical Internet.Internet structure is reconstructed from sampled traceroute paths, producing a good but imperfect representation because some edges may never be observed.Source: C. Technological networks · p. 8

D. Biological networks

  • Biological networks represent metabolic reactions, protein interactions, genetic regulation, food webs, neural connectivity, and vascular systems.Genetic regulatory networks model proteins as vertices with directed dependencies, and Kauffman’s random Boolean nets were an early large-scale modeling effort.Source: D. Biological networks · pp. 8–9

III. PROPERTIES OF NETWORKS

  • Random graphs place each possible edge independently with probability p, yielding binomial or asymptotically Poisson degree distributions and providing a benchmark for non-random real-network structure.Real networks differ from this benchmark in systematic ways that suggest mechanisms of network formation and potential uses of network structure.Source: §III · p. 9

A. The small-world effect

  • The small-world effect was directly demonstrated by Milgram’s experiments, in which letters reached designated targets in around six steps, and it has since been verified in many networks.Earlier anticipation came from Karinthy and Pool and Kochen.Source: A. The small-world effect · p. 9
  • Mean geodesic distance ℓ measures average shortest-path length between vertex pairs, including zero self-distances for mathematical convenience.Including self-distances changes ℓ by the factor (n − 1)/(n + 1), a correction of order n−1 that is often negligible.Source: A. The small-world effect · p. 9
  • Across published networks, ℓ is consistently small—much smaller than the number n of vertices.The reported values are compiled in Table II.Source: Table II · p. 10, A. The small-world effect · p. 11
  • For disconnected networks, ℓ is usually averaged only over vertex pairs with connecting paths; a harmonic-mean alternative avoids infinite distances by assigning disconnected pairs zero reciprocal contribution.The Table II values use the connected-pairs convention.Source: A. The small-world effect · p. 11
  • Networks exhibit the small-world effect when ℓ grows logarithmically or more slowly with n at fixed mean degree, with power-law networks increasing no faster than log n / log log n.Such short paths imply rapid spreading of information, disease, and other processes across networks.Source: A. The small-world effect · p. 11

B. Transitivity or clustering

  • For many networks, clustering remains C = O(1) as n →∞, whereas comparable random graphs have C = O(n−1), so real-world and random-graph values can differ by a factor of order n.Source: B. Transitivity or clustering · p. 12

C. Degree distributions

  • Most real-world degree distributions are highly right-skewed rather than Poisson, with many networks showing power-law tails and others exponential tails.Cumulative distributions preserve all degree data and reduce tail noise, though their adjacent points are statistically dependent.Source: C. Degree distributions · pp. 12–13
  • Directed networks are characterized by joint in- and out-degree distributions, whose correlations can contain information lost by reporting the two marginal distributions separately.Empirical studies have found strong in-degree and out-degree correlations in some networks.Source: C. Degree distributions · p. 13

1. Scale-free networks

  • Power-law degree distributions, often called scale-free, occur in many networks, but other networks show exponential, truncated-power-law, or subnetwork-specific forms.Power-law behavior has been observed in citation, Web, Internet, metabolic, telephone, and sexual-contact networks, while the power grid and railway networks show exponentials. Figure 6 shows power-law distributions for the Web, Internet, and yeast protein networks, a power-law tail for citations, an exponential for the power grid, and a truncated form for mathematician collaborations [182, 351, 74, 86, 416, 212].Source: §1 · pp. 13–14, Figure 6 · p. 14

2. Maximum degree

  • Maximum-degree estimates depend on network size and tail behavior: the rule nP_k = 1 gives a useful scale, but power-law tails exhibit very large fluctuations.For p_k ∼ k^-α, the corresponding estimate is k_max ∼ n^1/α; assuming independent degree sampling underlies the derivation, and the rule also applies to preferential-attachment networks.Source: §2 · pp. 14–15

D. Network resilience

Network resilience depends strongly on how vertices are removed: Internet and Web networks tolerate random removal but are highly vulnerable to targeted removal of high-degree vertices.

D. Network resilience

  • Network resilience concerns how vertex removal lengthens paths and eventually disconnects communicating vertex pairs.Source: D. Network resilience · p. 15
  • Targeted removal can represent deliberate attack, while vertex removal in contact networks can model vaccination and its effects on disease-spread paths.Source: D. Network resilience · p. 15
  • A few percent of targeted high-degree vertex removals can sharply increase mean distances and destroy essentially all communication, whereas random removal has little effect.Albert et al. found this pattern in both Internet and Web networks.Source: D. Network resilience · p. 15, Figure 7 · p. 15
  • Random removal is usually weakly disruptive because most vertices have low degree and lie on few paths between others.Source: D. Network resilience · p. 15
  • Studies differ in whether targeted removals use recalculated degrees after each deletion or the initial degree ordering.Source: D. Network resilience · p. 15
  • Broder et al. reported that destroying Web connectivity required removing all vertices with degree greater than five, an apparently conflicting result explained by the small fraction of such vertices.Source: D. Network resilience · pp. 15–16

E. Mixing patterns

Mixing patterns quantify how vertex types connect, while degree correlations distinguish assortative from disassortative network organization across network classes.

E. Mixing patterns

  • Assortative mixing measures preferential connections among similar vertex types, such as race, age, income, or network role.In a San Francisco study, couples preferentially selected partners of their own race.Source: E. Mixing patterns · p. 16
  • The normalized mixing matrix records edge fractions between vertex types and supports conditional neighbor probabilities P(j|i).Source: E. Mixing patterns · p. 16
  • The commonly used Q coefficient can be misleading because asymmetric mixing matrices yield two values and heterogeneous community sizes receive equal weighting.Source: E. Mixing patterns · pp. 16–17
  • The alternative assortativity coefficient is 0 for random mixing, 1 for perfect assortativity, and equals r = 0.621 for Table III data.Source: E. Mixing patterns · p. 17

F. Degree correlations

  • Degree correlations measure whether high-degree vertices connect to other high-degree or low-degree vertices; positive values indicate assortativity and negative values disassortativity.Source: F. Degree correlations · p. 17
  • Social networks are generally assortative by degree, whereas information, technological, and biological networks are generally disassortative.Source: F. Degree correlations · p. 17

G. Community structure

Community structure groups densely interconnected vertices and can be detected through clustering, while network navigation, resilience-related measures, motifs, and random-graph models extend structural analysis.

G. Community structure

H. Network navigation

  • Milgram’s experiment implies that social networks contain short paths that ordinary people can navigate using limited local information, unlike random graphs.Source: H. Network navigation · p. 19

I. Other network properties

  • Betweenness centrality, efficiency, and graph spectra characterize path disruption, diffusion or vibration modes, and vertex centrality.Source: §I · p. 20
  • Motif analysis finds recurrent subgraphs across network types and can suggest switching functions in genetic regulatory networks.Source: §I · p. 20

IV. RANDOM GRAPHS

  • Poisson random graphs are illuminating but inadequate for highly skewed real-world degree distributions, motivating generalized random graphs and configuration models.Source: §IV · p. 20

A. Poisson random graphs

The Poisson random graph models networks by independently connecting vertex pairs and reveals a phase transition to a giant component, while reproducing short paths but missing several real-network properties.

A. Poisson random graphs

  • A Poisson random graph independently connects each vertex pair with probability p, yielding a Poisson degree distribution when n is large at fixed mean degree z.The related G_n,m ensemble fixes the number of edges instead, while preserving most results in a straightforward way.Source: A. Poisson random graphs · pp. 20–21
  • At the phase transition, the graph changes from small finite components to a state containing an O(n) giant component, with smaller components remaining finite on average.The transition occurs at z = 1; the giant component is absent below it and nonzero above it.Source: A. Poisson random graphs · p. 21
  • The transition has critical exponents β = 1 and γ = 1; at z = 1, the mean largest component scales as O(n2/3), rather than O(n) above the transition.Source: A. Poisson random graphs · p. 21
  • The model reproduces the small-world effect through typical distances ℓ = log n / log z, but has vanishing clustering, Poisson degrees, random mixing, and no community structure.These mismatches make it a useful baseline but generally inadequate as a realistic model of real systems.Source: A. Poisson random graphs · pp. 21–22

B. Generalized random graphs

  • The configuration model generalizes the random graph by incorporating non-Poisson degree distributions while retaining a tractable random-network framework.The review proceeds to this model as the next treatment of generalized random graphs.Source: B. Generalized random graphs · p. 22

1. The configuration model

The configuration model generates graphs with a prescribed degree distribution by randomly pairing vertex stubs, and generating functions characterize component sizes and giant-component formation.

1. The configuration model

  • The configuration model assigns each vertex a degree from p_k, represents degrees as stubs, and pairs stubs uniformly to generate equally weighted graphs with that degree sequence.This construction provides a logical framework for studying networks beyond Poisson degree distributions.Source: §1 · p. 22
  • Following a random edge samples vertices in proportion to k p_k, so the relevant excess-degree distribution is q_k rather than the vertex degree distribution p_k.This size bias is central to the model’s generating-function analysis.Source: §1 · p. 22
  • Generating functions H_0 and H_1 describe component sizes reached from random vertices and edges, and their self-consistency equations yield the full component-size distribution.The mean size of non-giant components below the transition follows from solving these equations.Source: §1 · p. 23
  • A giant component appears when the mean number of second neighbors exceeds the mean number of first neighbors, with the condition expressed through the degree distribution.Above the transition, u = G_1(u) determines the fraction outside the giant component, and S gives its size.Source: §1 · p. 23
  • The configuration model qualitatively resembles the Poisson random graph, exhibiting a continuous transition with β = γ = 1 and τ = 5, governed by z2/z1.At the transition, a giant component appears and the mean size of non-giant components diverges.Source: §1 · p. 23
  • Its clustering coefficient is C = z/n multiplied by a factor involving ⟨k^2⟩/⟨k⟩^2, which can make clustering non-negligible for highly skewed degree distributions.The model’s tree-like small components rely on loops becoming rare as n grows, an assumption that is generally false in real networks.Source: §1 · pp. 22–23

2. Example: power-law degree distribution

For power-law degree distributions, the configuration model predicts a critical exponent separating networks with and without giant components and shows that degree skew can sustain substantial clustering.

2. Example: power-law degree distribution

  • The giant-component transition occurs at the critical exponent α_c = 3.4788…, with a giant component below this value and none above it.For α < 2, the giant component occupies the entire graph in the large-network limit; for 2 < α < α_c, it is nonzero but not exhaustive.Source: §2 · p. 24
  • For α > 7/3, clustering C tends to zero as the graph becomes large, but for α < 3 it decays more slowly than the Poisson random graph’s C ∼ n−1.Source: §2 · p. 24
  • For α < 7/3, the clustering coefficient becomes constant or logarithmic with graph size and increases with size when α < 7/3.Thus substantial clustering can arise even when connections are otherwise random in scale-free networks with small α.Source: §2 · p. 24
  • The generating-function results break down for α < 7/3 because their assumption of negligible short loops fails, while imposing a degree cutoff restores vanishing clustering but is artificial for real networks.The limitation reflects the difference between the model’s locally tree-like structure and empirical power-law networks.Source: §2 · p. 24

3. Directed graphs

Directed random graphs generalize degree distributions to joint in- and out-degree structure, enabling analysis of in-, out-, and strongly connected giant components.

3. Directed graphs

  • Directed vertices have in-degree j and out-degree k, so their degree distribution is a joint distribution p_jk with a two-variable generating function.Source: §3 · p. 24
  • Giant in-, out-, and strongly connected components emerge together at a single transition in directed random graphs with a specified degree distribution.Source: §3 · p. 24
  • Their sizes are obtained from generating functions as S_out = 1 − F_0(u), S_in = 1 − G_0(v), and S_str = 1 − G(u,1) − G(1,v) + G(u,v).Source: §3 · p. 24

4. Bipartite graphs

The review extends random-graph analysis to bipartite and more general mixing structures, then examines exponential random graphs as flexible but analytically difficult models of transitivity.

4. Bipartite graphs

  • Bipartite graphs separate vertices into two types, with edges only between unlike types; affiliation networks are a principal application.Source: §4 · pp. 24–25
  • Bipartite networks have two degree distributions whose means satisfy μ/M = ν/N, and a giant component appears when f′_1(1)g′_1(1) = 1.Source: §4 · p. 25
  • One-mode projections of bipartite graphs can retain nonzero clustering in the large-system limit, unlike the original sparse random-graph expectation.Source: §4 · p. 25
  • Degree-correlated random graphs generalize giant-component criteria to matrix conditions, with the transition occurring when det(I − m) = 0.Source: §4 · p. 25

V. EXPONENTIAL RANDOM GRAPHS AND MARKOV GRAPHS

  • Exponential random graphs assign probabilities to graphs using measurable properties such as edges, degrees, or triangles and parameters β_i, with the free energy generating observable expectations.Source: §V · p. 26
  • Analytic treatment remains difficult because the field-theoretic program is largely intractable, leaving calculations for most exponential random-graph ensembles open.Source: §V · p. 26
  • Monte Carlo Markov-chain methods can sample exponential random-graph ensembles using local moves and acceptance probabilities based on graph-property changes.Source: §V · pp. 26–27
  • Positive triangle terms can cause exponential random graphs to condense into nearly complete cliques, unlike the distributed transitivity observed in real networks.Source: §V · p. 27

VI. THE SMALL-WORLD MODEL

The small-world model interpolates between a regular lattice and a random graph by rewiring or adding shortcuts, producing an intermediate regime with high clustering and short paths.

VI. THE SMALL-WORLD MODEL

  • The model starts from a low-dimensional lattice and introduces a low density of shortcuts connecting remote regions.Source: §VI · p. 27
  • At intermediate rewiring probability p, numerical simulations find simultaneously low path lengths and high transitivity, unlike either endpoint.Source: §VI · p. 27, Figure 12 · p. 28
  • The original construction is analytically cumbersome because it rewires one edge end while forbidding self-edges and duplicate edges.Source: §VI · p. 27
  • The shortcut-only variant adds random edges without rewiring, preserving lattice connectivity and keeping mean vertex distance formally finite.Source: §VI · p. 28

A. Clustering coefficient

B. Degree distribution

  • The shortcut-only degree distribution has a minimum degree 2k and a binomially distributed number of shortcuts, whereas the rewired version has a lower cutoff k.Source: B. Degree distribution · pp. 28–29

C. Average path length

Average path length crosses from large-world to small-world behavior as shortcuts or system size increase, while network-growth models seek mechanisms generating structural properties such as transitivity and skewed degrees.

C. Average path length

  • The small-world model has no exact general solution for mean path length ℓ, but scaling forms and approximations describe its parameter dependence.Source: C. Average path length · p. 29
  • The path length follows a crossover scaling relation governed by a correlation length ξ that diverges as p approaches zero.Source: C. Average path length · p. 29
  • Renormalization-group analysis gives τ = 1 for ξ ∼ p^-τ, correcting the conjectured value τ = 2/3.Source: C. Average path length · p. 29
  • The scaling variable Lkp equals the mean number of shortcuts, so normalized path length depends on shortcut count for fixed k.Source: C. Average path length · p. 29
  • The small-world model has supported studies of percolation, diffusion, epidemics, oscillators, games, and spin systems.Source: C. Average path length · p. 29

VII. MODELS OF NETWORK GROWTH

  • Network-growth models add vertices and edges through processes such as triadic closure, which completes triangles and increases transitivity.Source: §VII · p. 30
  • The most extensively studied growth models aim to explain highly skewed degree distributions, including Price and Barabási–Albert models.Source: §VII · p. 30

A. Price’s model

Price applied cumulative advantage to growing citation networks, modeling attachment probability as proportional to existing in-degree with an offset. The model yields a power-law degree distribution whose exponent depends on mean out-degree.

A. Price’s model

  • Price’s network model applies cumulative advantage to citation growth, with new edges attaching to existing vertices in proportion to k + 1.The offset prevents vertices with zero in-degree from having permanently zero attachment probability.Source: A. Price’s model · pp. 30–31
  • The model treats new vertices as papers with fixed out-degree, whose mean m is also the network’s mean in-degree and may be non-integer or below 1.Source: A. Price’s model · pp. 30–31
  • In the large-network limit, Price’s degree distribution has a power-law tail with exponent α = 2 + 1/m, typically between 2 and 3.Price’s comparison with Science Citation Index data suggested that m could reproduce the observed citation distribution.Source: A. Price’s model · p. 31
  • The exponent remains α = 2 + 1/m for a general offset k0, so the choice k0 = 1 does not determine the asymptotic exponent.Source: A. Price’s model · p. 31
  • Price’s analytic treatment preceded computational simulation, while later work used simulations and shifted attention toward the Barabási–Albert model.Source: A. Price’s model · p. 31

B. The model of Barab´asi and Albert

The Barabási–Albert model simplifies Price’s directed process by using undirected edges and fixed integer degree m, retaining degree-proportional attachment. It produces a universal α = 3 power law, while also generating age and degree correlations that can conflict with Web data.

B. The model of Barab´asi and Albert

  • Unlike Price’s model, Barabási–Albert uses undirected edges and adds exactly an integer m ≥ 1 degree to every new vertex, avoiding the zero-citation problem.The simplification sacrifices directed-network realism but gives each new vertex nonzero attachment probability.Source: B. The model of Barab´asi and Albert · p. 32
  • The Barabási–Albert model produces a power-law degree distribution pk ∼ k^-3 with the single fixed exponent α = 3.This result follows from its stationary master-equation solution.Source: B. The model of Barab´asi and Albert · p. 32
  • The model’s overall power-law distribution is driven primarily by early vertices, whose expected degrees exceed those of vertices added later.For fixed age, the degree distribution is exponential, with a degree scale diverging as the vertex approaches the network’s earliest additions.Source: B. The model of Barab´asi and Albert · p. 33
  • Adamic and Huberman found no age–degree correlation in the real Web, indicating that Web dynamics may be more complicated than this simple model.This discrepancy does not rule out preferential attachment as an explanation for Web power laws.Source: B. The model of Barab´asi and Albert · p. 33
  • The model has non-trivial degree correlations between adjacent vertices, even though their asymptotic linear correlation coefficient tends to zero.Source: B. The model of Barab´asi and Albert · p. 33
  • An array-based simulation reduces preferential-attachment generation from O(n^2) overall time to O(n) by sampling vertices according to repeated degree entries.Source: B. The model of Barab´asi and Albert · p. 33
  • Empirical studies of citation, Internet, and collaboration networks found that newly acquired edges were roughly proportional to previously existing edges.These findings support linear preferential attachment as a reasonable approximation in those networks.Source: B. The model of Barab´asi and Albert · p. 34

C. Generalizations of the Barab´asi–Albert model

Generalizations modify attachment offsets, nonlinear degree dependence, changing mean degree, edge turnover, and vertex fitness. These extensions tune the degree-distribution exponent or produce qualitatively different outcomes such as stretched exponentials and condensation.

C. Generalizations of the Barab´asi–Albert model

  • An attachment offset k0 changes the asymptotic exponent to α = 3 + k0/m, with negative offsets proposed as an explanation for observed α < 3.Source: C. Generalizations of the… · p. 34
  • For attachment probability proportional to k^γ, γ = 1 gives a power law, γ < 1 gives a power law with a stretched-exponential factor, and γ > 1 causes condensation.For γ > 2, the condensate can connect to every other vertex with nonzero probability, while remaining vertices have exponentially decaying degree distributions.Source: C. Generalizations of the… · p. 34
  • If the mean number of new edges grows with network size as n^a, the resulting exponent becomes α = 2 + B(1 + a)/(1 − Ba).Source: C. Generalizations of the… · p. 34
  • Allowing links to appear, disappear, or move among existing vertices preserves power laws across some parameter ranges but can also produce exponential distributions.These changes address the Web’s ongoing link creation and removal, which Price’s model excludes.Source: C. Generalizations of the… · p. 35
  • Fitness-weighted attachment yields power laws when the fitness distribution has finite support, but infinite support produces winner-takes-all dominance by the highest-fitness vertex.The attachment probability is proportional to η_i k_i, combining intrinsic attractiveness with degree.Source: C. Generalizations of the… · p. 35
  • Fitness-based extensions preserve power laws for suitable parameter values even when fitness enters additively or preferential attachment is removed.Source: C. Generalizations of the… · p. 35

D. Other growth models

The review develops growth models that address shortcomings of preferential-attachment models, including component structure, directionality, and degree distributions. It also examines vertex copying as an alternative mechanism for producing power-law networks and connects network structure to processes such as percolation and failure.

D. Other growth models

  • The original Barabási–Albert model lacks several features of the real Web, including directionality, realistic attachment, cycles, separate components, and variable out-degree.These limitations motivate more elaborate growth models tailored to Web structure.Source: D. Other growth models · p. 35
  • Callaway et al.’s growth model allows multiple components and exhibits a phase transition at finite m where a giant component appears.The model adds a mean number m of undirected edges per new vertex, and the transition occurs precisely at m = 1/2.Source: D. Other growth models · p. 36
  • Directed growth models can reproduce Web-like features, including separate components and power laws in both in- and out-degree distributions.Krapivsky and Redner’s model also permits edges to be added after vertex creation and can tune both exponents to observed values.Source: D. Other growth models · pp. 36–37

E. Vertex copying models

  • Copying offers a plausible mechanism for power-law protein-interaction networks through gene duplication, although its role in Web growth remains uncertain.Duplicated genes initially inherit the interaction edges of their originals and may later diverge through evolution.Source: E. Vertex copying models · p. 37
  • Vertex-copying models generate power-law degree distributions because copied targets receive attachment probability proportional to their current degree.With mostly copied targets, the predicted exponent lies in the observed range 2 ≤ α ≤ 3.Source: E. Vertex copying models · p. 37

VIII. PROCESSES TAKING PLACE ON NETWORKS

  • Network-process research studies how topology affects failures, epidemics, and other dynamics, with percolation modeling occupied or unoccupied vertices or edges.Site and bond percolation focus respectively on clusters of occupied vertices and vertices connected by occupied edges.Source: §VIII · pp. 37–38, Figure 13 · p. 38

A. Percolation theory and network resilience

Percolation theory provides a framework for analyzing network resilience under random or degree-targeted failure. The review shows that power-law networks can be robust to random deletion yet highly vulnerable to targeted attacks, while cascading failures require additional threshold-based analysis.

A. Percolation theory and network resilience

  • Random vertex failure is equivalent to site percolation, with the surviving giant component representing the vertices that can still communicate.Generating-function methods determine whether the occupied subnetwork retains a giant component.Source: A. Percolation theory and network… · p. 38
  • Power-law networks are highly robust to random vertex removal when α ≤ 3 because their percolation threshold is zero or negative.More generally, the threshold is nonpositive for degree distributions with a diverging second moment.Source: A. Percolation theory and network… · p. 38
  • Callaway et al.’s generalized formalism allows occupation probability q_k to depend on vertex degree, enabling analysis of degree-targeted removal.Removing vertices in decreasing degree order reproduces the targeted-attack setting studied for the Web.Source: A. Percolation theory and network… · pp. 38–39
  • Less than 3% of the highest-degree vertices need removal to destroy the giant component in the configuration-model power-law networks shown in Fig. 14.For most power-law exponents, the required fraction is significantly smaller.Source: A. Percolation theory and network… · p. 39, Figure 14 · p. 39
  • Percolation thresholds also depend on network correlations and geography, so a divergent degree-distribution second moment does not universally imply zero threshold.Positive or negative degree correlations and spatial constraints can respectively lower or restore a nonzero threshold.Source: A. Percolation theory and network… · pp. 39–40
  • Cascading failures arise when an initial failure redistributes load, pushes neighboring elements beyond capacity, and triggers further failures.Watts’s model maps cascade spreading to percolation among vulnerable vertices, while final cascade sizes require numerical simulation.Source: A. Percolation theory and network… · p. 40

B. Epidemiological processes

  • Network studies also apply these ideas to disease and information spreading over contact networks.Examples include sexual-contact networks for sexually transmitted diseases and email networks for computer viruses.Source: B. Epidemiological processes · p. 40

1. The SIR model

The review develops network-based epidemic models by mapping SIR dynamics to bond percolation and approximating SIS dynamics with mean-field methods. It also connects network structure to exhaustive search through eigenvector-based ranking algorithms.

1. The SIR model

  • SIR epidemics on networks map exactly to bond percolation, linking outbreak sizes to cluster sizes, epidemic thresholds to percolation transitions, and giant components to epidemic sizes.The mapping describes long-time outcomes but not the temporal progression of outbreaks.Source: §1 · p. 41
  • Power-law networks with degree-distribution exponent below 3 have no non-zero SIR epidemic threshold, although correlations, low-dimensional embedding, or high transitivity can restore one.This revises the broad conclusion that diseases always spread on scale-free networks.Source: §1 · p. 41
  • Targeted vaccination of highest-degree vertices is expected to be particularly effective, while acquaintance vaccination finds such vertices more effectively than random vaccination.Following a random person’s friend exploits the degree-biased probability of reaching high-degree vertices.Source: §1 · p. 42

2. The SIS model

  • The SIS mean-field treatment allows infection rates to vary by degree but assumes a common neighbor-infection probability, so properties near the phase transition may be quantitatively mispredicted.The approximation is intended primarily to capture qualitative behavior.Source: §2 · p. 42
  • For SIS dynamics on power-law networks, mean-field analysis predicts no non-zero epidemic threshold, with persistence robust to random vaccination but highly vulnerable to vaccinating highest-degree vertices.The same approximation finds that degree assortativity does not produce a non-zero threshold for SIS, contrasting with some SIR results.Source: §2 · p. 43

1. Exhaustive network search

  • Exhaustive network search ranks Web pages using edge structure: Brin–Page uses the leading adjacency-matrix eigenvector, whereas Kleinberg separates authority and hub weights through A A^T.Kleinberg’s method is especially suited to directed networks but had not been implemented in a commercial search engine at the time described.Source: §1 · pp. 43–44

2. Guided network search

Guided search reduces network exploration by using local content or degree information, while network design can make greedy navigation efficient. The review also surveys phase transitions, other dynamical processes, and open methodological gaps in network science.

2. Guided network search

  • Guided Web crawlers focus agents on locally clustered promising pages, whereas degree-guided peer-to-peer search exploits skewed degree distributions and passes queries toward higher-degree vertices.The crawler assumes topic-related pages cluster locally; the degree-guided algorithm uses recursive backtracking to avoid dead ends.Source: §2 · pp. 44–45
  • Adamic et al.’s degree-guided search improves on O(n) breadth-first search, requiring n^(α−2)/(α−1) steps for 2 ≤ α ≤ 3 under the stated scaling assumptions.The predicted range is between O(n^1/2) and O(log n), with stronger gains for smaller α.Source: §2 · p. 45
  • Kleinberg’s lattice model achieves optimal greedy-search performance at α = 2 in two dimensions, where targets can be found in O(log n) steps; more generally, the optimum is α = d.Shortcut probability scales as r^−α, and simulations confirmed the predicted two-dimensional behavior.Source: §2 · p. 45
  • Hierarchical social-distance models explain greedy navigation using overlapping or disjoint categories such as occupation, location, and interests, with shorter social distances receiving more edges.The hierarchical model is specialized, while overlapping-category extensions produce qualitatively similar search behavior.Source: §2 · p. 46, Figure 15 · p. 46

D. Phase transitions on networks

  • Network phase-transition behavior depends strongly on topology: power-law degree distributions affect critical behavior, while small-world colorability is easiest at low and high shortcut densities but harder at intermediate density.Vertex-cover solutions are also harder to find under strong degree correlations.Source: D. Phase transitions on networks · pp. 46–47

E. Other processes on networks

  • Other studied network processes include diffusion, random walks, graph-Laplacian spectra, Boolean networks, cellular automata, opinion models, games, oscillators, neural networks, and self-organized criticality.These investigations are described as preliminary in several areas.Source: E. Other processes on networks · p. 47

IX. SUMMARY AND DIRECTIONS FOR FUTURE RESEARCH

  • The review concludes that real networks commonly show high clustering and skewed degree distributions, while network analysis still lacks a systematic framework for identifying which structural measures matter for particular questions.Future work includes more sophisticated models that explain topology and support studies of processes on networks.Source: §IX · pp. 47–48
Loading cond-mat/0303516v1…