PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolution of networks

S. N. Dorogovtsev, J. F. F. Mendes

arXiv:cond-mat/0106144v2cond-mat.stat-mechq-bio

TL;DR

The paper reviews how statistical physics can explain the structure and evolution of large complex networks across several application domains. It surveys scaling, connectivity, growth, percolation, and network models, reporting scale-free organization, short path lengths, and related structural patterns while noting the review’s incomplete coverage.

  • Problem

    Large evolving networks have complex topologies and processes that require systematic understanding across communications, biology, economics, and social systems.

    Source: §I · p. 2

  • Method

    The paper reviews evolving networks using statistical-physics ideas, models, simulations, analytical approaches, and applications to particular natural networks.

    Source: §I · p. 2, §5 · p. 14, H. “Condensation” of edges · p. 38

  • Results

    The review identifies scale-free structure, short distances, accelerated growth, cutoff effects, and network-dependent spreading behavior among evolving-network phenomena.

    Source: §1 · p. 10, D. Scaling relations and cutoff · p. 27, J. Accelerated growth of networks · p. 39

  • Takeaways & Limitations

    Network growth and structure connect to broader problems in non-equilibrium physics, econophysics, evolutionary biology, and related fields.

    Source: §I · p. 2

    The review omits several recent topics, including random, intentional, and adaptive walks and shortest-path participation distributions.

    Source: §XIII · p. 58

Abstract

from arXiv · show

We review the recent fast progress in statistical physics of evolving networks. Interest has focused mainly on the structural properties of random complex networks in communications, biology, social sciences and economics. A number of giant artificial networks of such a kind came into existence recently. This opens a wide field for the study of their topology, evolution, and complex processes occurring in them. Such networks possess a rich set of scaling properties. A number of them are scale-free and show striking resilience against random breakdowns. In spite of large sizes of these networks, the distances between most their vertices are short -- a feature known as the ``small-world'' effect. We discuss how growing networks self-organize into scale-free structures and the role of the mechanism of preferential linking. We consider the topological and structural properties of evolving networks, and percolation in these networks. We present a number of models demonstrating the main features of evolving networks and discuss current approaches for their simulation and analytical study. Applications of the general results to particular networks in Nature are discussed. We demonstrate the generic connections of the network growth processes with the general problems of non-equilibrium physics, econophysics, evolutionary biology, etc.

I. INTRODUCTION

The review frames evolving networks as a statistical-physics problem spanning communications, biology, economics, and social systems. It surveys structural characteristics and the empirical and mathematical foundations used to analyze these networks.

I. INTRODUCTION

  • Large communications networks motivated study of evolving-network structure, topology, organization, and internal processes for effective operation and safety.Internet and WWW data became especially valuable because their large size and extensive documentation enabled more reliable structural investigation.Source: §I · p. 2, §II · p. 2
  • The review applies statistical-physics ideas to network evolution across computer science, mathematics, engineering, biology, economics, and social sciences.It focuses on evolving networks rather than Boolean and neural networks.Source: §I · p. 2

II. HISTORICAL BACKGROUND

  • Early graph theory mainly treated Poisson random graphs, while evolving scale-free networks required attention to how structure forms during growth.Recent mathematical results also considered graphs with arbitrary connection distributions.Source: §II · p. 2
  • Experiments from 1997–1999 revealed power-law connection distributions and surprisingly small average shortest-path lengths in communications networks.These findings prompted intensive study of evolving networks in communications, biology, and public relations.Source: §II · p. 2

A. Degree

  • Degree distributions summarize local connectivity, and without statistical vertex correlations they can determine the structure of a random network.For directed networks, total degree combines in-degree and out-degree: k = k_i + k_o.Source: A. Degree · p. 3

B. Shortest path

  • Average shortest-path length can remain small in very large networks, producing the small-world effect through approximately ℓ ∼ ln N / ln z_1.Shortest paths are defined over connected vertex pairs, with directed paths potentially asymmetric.Source: B. Shortest path · p. 3

C. Clustering coefficient.

  • The clustering coefficient measures the fraction or probability of connections among a vertex’s nearest neighbors, capturing local cliquishness.It equals one for a complete graph and zero for tree-like graphs; in classical random graphs, C = z_1/(N − 1).Source: clustering coefficient · p. 4

D. Size of the giant component

  • A giant component is a connected cluster containing a finite fraction of vertices in the large-network limit, with directed networks also allowing strong and weak variants.Accurate measurement is difficult because finite-size effects can be strong.Source: D. Size of the giant component · p. 4

IV. NOTIONS OF EQUILIBRIUM AND NON-EQUILIBRIUM NETWORKS

This section distinguishes equilibrium from growing non-equilibrium networks and examines how growth produces persistent structural inhomogeneity. It surveys structural patterns in citation, collaboration, and Internet networks, including degree distributions, correlations, clustering, path lengths, preferential attachment, geographic organization, and basin scaling.

IV. NOTIONS OF EQUILIBRIUM AND NON-EQUILIBRIUM NETWORKS

  • Growing networks are non-equilibrium because adding vertices and edges makes older vertices more connected, while equilibrium requires edge deletion to remove persistent inhomogeneity.A fixed-size random graph can approach equilibrium through random edge addition, but a growing graph cannot equilibrate merely by stopping vertex growth; old edges must also disappear.Source: §IV · p. 5
  • Equilibrium random networks are statistical ensembles of edge configurations, with the degree distribution determining the ensemble, although rigorous finite-size construction for arbitrary degree distributions remains open.The Molloy–Reed procedure assigns degrees from P(k) and randomly pairs quill ends, but yields a particular realization rather than the full finite-size ensemble.Source: §IV · pp. 5–6

A. Networks of citations of scientific papers

  • Citation networks grow only by adding references from new papers to older ones, and empirical citation allocation is proportional to current degree, indicating linear preferential attachment.Old papers are not updated, so new links between existing vertices cannot form; the analyzed sample contained 1,736 papers and 83,252 citations.Source: A. Networks of citations of scientific… · pp. 6–7, Figure 2 · p. 6

B. Networks of collaborations

  • Collaboration networks exhibit short paths and high clustering, while reported degree distributions range from power laws to exponentials depending on projection and dataset choices.The movie-actor graph has average shortest path 3.65 and clustering coefficient C = 0.79 versus 0.00027 for its classical random-graph counterpart; alternative data give C = 0.199.Source: B. Networks of collaborations · p. 7
  • Collaboration networks become denser as they grow, with declining path lengths and clustering coefficients, preferential attachment approximately proportional to k^0.8±0.1, and existing-pair linking proportional to the product of endpoint degrees.Linear preferential attachment is observed until high degrees, after which it saturates or declines in the Los-Alamos and Medline networks.Source: B. Networks of collaborations · pp. 7–8

1. Structure of the Internet

  • At the inter-domain level, the Internet is sparse and small-world, with average shortest paths near 4 and degree distributions reported as power laws with γ approximately 2.2–2.3.From 1997 to 1998, average degree rose from 3.42 to 3.76 while maximum degree rose from 590 to 979; later data show increasing density and high clustering despite short paths close to classical random graphs.Source: §1 · pp. 8–9
  • The ratio of new links between new and old vertices to links between already existing vertices rose from 0.34 in 1997 to 0.48 in 1998 and 0.53 in 1999, distinguishing the Internet from citation graphs.Source: §1 · p. 9
  • The Internet’s degree distributions follow a power law with exponent γ ≈2.2, while nearest-neighbor degree decreases approximately as a power law with exponent 0.5.The decreasing knn(k) indicates strong degree correlations: high-degree vertices usually have weakly connected neighbors, and vice versa.Source: §1 · p. 9
  • New-edge attachment probability is a linear function of vertex degree, indicating preferential linking in Internet maps.Source: §1 · p. 9
  • Population, router, and AS densities form spatial fractals with dimension approximately 1.5, and the average shortest distance between two routers is approximately 9.The analysis covered North America and examined maps of AS and 228 265 routers.Source: §1 · p. 10
  • Internet basin sizes follow a power-law distribution P(n) ∝n−τ with τ = 1.9 ± 0.1, analogous to scaling in fractal river networks.Source: §1 · p. 10

2. Structure of the WWW

The WWW grows through adding accessible pages and updating existing pages, producing a directed structure with giant connected components, short paths, and heterogeneous degree distributions. Empirical studies report power-law patterns across multiple Web levels, while finite size and fitting limitations constrain interpretation.

2. Structure of the WWW

  • New pages become accessible through at least one incoming hyperlink, while old pages can gain new links through updates, making Web growth more complex than citation-network growth.Pages may contain several, or in principle no, references to existing documents before being linked from an accessible page.Source: Figure 5 · p. 10, §2 · p. 10
  • The Web grew from 203 × 10^6 pages and 1466 × 10^6 links in May 1999 to 271 × 10^6 pages and 2130 × 10^6 links in October, adding 9.8 links per page.The number of hyperlinks grew faster than the number of vertices.Source: §2 · p. 10
  • The Web’s in- and out-degree distributions followed power laws with exponents γ_i = 2.1 and γ_o = 2.7, while links formed bipartite hub-authority subgraphs used for cyber-community indexing.Bipartite subgraph counts showed power-law-like behavior in authorities and exponential behavior for small hub counts, although the data were poor.Source: §2 · pp. 10, 12
  • In May 1999, 186 × 10^6 of 203 × 10^6 Web pages belonged to the GWCC, which contained GSCC, GIN, GOUT, and tendrils.The component sizes were 56 × 10^6 GSCC, 99 × 10^6 GIN, 99 × 10^6 GOUT, and 44 × 10^6 tendrils.Source: §2 · p. 11
  • Directed paths existed between an estimated 24% of random page pairs, with average shortest lengths 16 directed and 7 undirected when paths existed.The maximal shortest directed path exceeded 500, while the GSCC maximum was 28.Source: §2 · p. 11
  • Power-law claims require caution because log-log linear fits often cover narrow ranges, strong fluctuations obscure functional forms, and finite network sizes can produce implausible interpretations.Cumulative distributions are commonly used to reduce fluctuations, but finite-size effects remain important.Source: §2 · p. 12

1. Structure of neural networks

The review compares network structures across biological, ecological, linguistic, engineered, and classical random systems. These examples commonly combine short paths or high clustering with heterogeneous degree patterns, while several measurements remain limited by small or incomplete datasets.

1. Structure of neural networks

  • C. elegans has 282 neurons, average degree 14, average path length 2.65, and clustering coefficient 0.26, far above the classical random-graph value.Its exponential degree distributions coexist with a small-world structure.Source: §1 · p. 12

2. Networks of metabolic reactions

  • Metabolic reaction networks of 43 organisms had sizes 200–800, average shortest paths about 3, and reported in- and out-degree exponents γ_i ≈ γ_o ≈ 2.2.For Escherichia coli, the undirected network had clustering coefficient C ≈ 0.3 versus 0.025 for the corresponding random network.Source: §2 · p. 13

3. Protein networks

  • The yeast protein-interaction network was interpreted as scale-free with an exponential cutoff near k_c ≈20, and random deletions were tolerated more than removal of highly connected proteins.Deleting one of the most connected proteins, with more than 15 links, was lethal with high probability.Source: §3 · p. 13

4. Ecological and food webs

  • Food webs were dense and extremely short-range, with edge densities 0.061–0.32 and average path lengths 1.44–2.55, while clustering exceeded random-graph values but path lengths did not.The Ythan estuary and Silwood park webs were fitted by power laws with γ ≈ 1.0 and γ ≈ 1.1, although exponential-like interpretations were also reported.Source: §4 · pp. 13–14

5. Word Web of human language

  • The Word Web contained about 470,000 words and showed two degree-distribution power-law regions, with exponents approximately 1.5 at low degree and 3 at high degree.A simple evolutionary model described the complex empirical distribution without fitting.Source: §5 · p. 14

E. Electronic circuits

  • Large electronic circuits had shortest paths close to corresponding random graphs, clustering more than an order of magnitude higher for N > 10^4, and power-law degree tails with γ ≈3.0.The largest circuits had maximum component degree approaching 10^2.Source: E. Electronic circuits · pp. 14–15

VI. CLASSICAL RANDOM GRAPHS, THE ERD¨OS-R´ENYI MODEL

  • The Erdős–Rényi model fixes N and connects vertex pairs independently with probability p, yielding Poisson-like degrees, logarithmic path lengths, and a giant component above p_c ≈1/N.Its percolation threshold corresponds to mean degree k_c = 1.Source: §VI · p. 15

VII. SMALL-WORLD NETWORKS

  • Watts–Strogatz small-world networks combine short average paths with high clustering, but the review notes that this definition excludes some random or lattice-based networks and represents only one construction.The model constructs networks from ordered lattices through random rewiring or added random connections.Source: §VII · pp. 15–16

A. The Watts-Strogatz model and its variations

The section develops small-world networks through rewiring, shortcuts, and growth, showing that global path lengths can collapse while local clustering remains high. Exactly solvable variants expose the crossover and connect large clustering to neighborhood-based growth.

A. The Watts-Strogatz model and its variations

  • The Watts-Strogatz construction rewires a periodic one-dimensional lattice with probability p, interpolating between a regular lattice and a classical random graph.Adding shortcuts instead of rewiring preserves the model’s main features, and the average path length is described through a crossover scaling function.Source: A. The Watts-Strogatz model and its… · pp. 16–17
  • A few rewired edges reduce the average shortest-path length to classical-random-graph values while local clustering remains close to that of the regular lattice.The global change begins around pzL ∼1, corresponding to roughly one shortcut, while local characteristics remain nearly unchanged.Source: A. The Watts-Strogatz model and its… · pp. 16–17
  • In disease-spreading dynamics, the infected fraction initially grows as t^d, then increases exponentially before saturating at ni/L = 1.The model also supports analyses of percolation and diffusion.Source: A. The Watts-Strogatz model and its… · pp. 17–18

B. The smallest-world network

  • The smallest-world model adds a central vertex-linked shortcut structure and has an exactly calculable shortest-path distribution in the scaling limit.With ρ = pL fixed, the distribution is Q(z, ρ) = 2[1 + 2ρz + 2ρ^2z(1 − 2z)]e^−2ρz; paths rapidly saturate as pk grows.Source: B. The smallest-world network · pp. 18–19
  • The smallest-world crossover sharply decreases ℓ while local properties remain close to the initial regular structure, although the toy model does not approach a classical random network at large p.At p = 1, the average path length is ℓ = 1.Source: B. The smallest-world network · pp. 18–19

C. Other possibilities to obtain large clustering coefficient

  • A growing network can combine small-world structure and large clustering by attaching each new vertex to a randomly chosen triple of nearest neighbors.The construction grows through both new vertices and new edges, unlike the fixed-vertex Watts-Strogatz setup.Source: C. Other possibilities to obtain large… · p. 20
  • The triple-neighbor growth rule yields a clustering coefficient near 1/2, much larger than the characteristic value k/t of classical random graphs.The mechanism is simultaneous attachment to mutually nearby old vertices, which creates triangles as the network grows.Source: C. Other possibilities to obtain large… · p. 20

VIII. GROWING EXPONENTIAL NETWORKS

Random attachment in growing networks produces exponential degree distributions, whereas preferential linking generates scale-free distributions. Master-equation analyses generalize these results and identify how attractiveness, age, and finite-size effects shape network structure.

VIII. GROWING EXPONENTIAL NETWORKS

  • Randomly attaching each new vertex to an old vertex produces an exponential degree distribution and logarithmic average path length, ℓ ∼ ln t.The distribution differs from the Poisson law of classical random graphs but remains rapidly decreasing.Source: §VIII · pp. 20–21
  • In random-attachment growth, the oldest vertices are statistically richest, but their average degree increases only weakly near the network’s oldest vertex.The same exponential behavior persists when each new vertex has any fixed number of randomly chosen connections.Source: §VIII · p. 21

A. Barab´asi-Albert model and the idea of preferential linking

  • Preferential linking changes the outcome: attaching with probability proportional to degree produces a scale-free distribution P(k) ∝ k^−3.The BA model implements this rule with attachment probability k/(2t), and the exponent γ = 3 is exact.Source: A. Barab´asi-Albert model and the idea… · pp. 21–22

B. Master equation approach

  • The master-equation approach solves broader preferential-linking models and shows that the exponent γ varies with additional attractiveness, with γ > 2 for constant-average-degree networks.For the BA specialization, the exact solution recovers exponent 3.Source: B. Master equation approach · pp. 22–23
  • The generalized model assumes m incoming targets are chosen according to q(s) + A, where A is additional attractiveness and the source locations do not affect the resulting in-degree distribution.Setting A = m recovers the BA model when each new vertex supplies all m edges.Source: B. Master equation approach · p. 22, Figure 20
  • Individual-vertex in-degree distributions have exponential tails, while old vertices’ mean in-degree diverges as s^−β with β = 1/(1 + a).For the BA model, β = 1/2, making the age effect pronounced.Source: B. Master equation approach · p. 23

C. A simple model of scale-free networks

This section presents exactly analyzable growing networks that generate scale-free behavior without always imposing preferential attachment explicitly. Their finite-size distributions, motif statistics, clustering, and discrete degree spectra expose both the strengths and boundaries of these constructions.

C. A simple model of scale-free networks

  • A network formed by attaching each new vertex to both ends of a randomly chosen edge has a stationary degree distribution approaching the BA form with γ = 3.The master equation is exact at finite times, and the model’s attachment probability is proportional to vertex degree because edges are selected uniformly.Source: C. A simple model of scale-free networks · pp. 24–25
  • Finite-size effects persist through a scaling function of k/√t, and the power-law regime is observable only for 1 ≪ k ≪ √t.The cutoff hump depends on the initial configuration and remains visible at every network size.Source: C. A simple model of scale-free networks · p. 25
  • The associated growing directed network contains a number of bipartite subgraphs proportional to network size, with stationary hub distribution G(h) = 2^−h.This behavior agrees with estimates for citation graphs and measurements of bipartite subgraphs in the WWW.Source: C. A simple model of scale-free networks · pp. 25–26
  • A deterministic edge-subdivision model produces a discrete degree spectrum whose counts decrease as a power law, so it can be called scale-free despite missing intermediate degrees.Its clustering coefficient approaches C → 4/5 as t →∞.Source: C. A simple model of scale-free networks · p. 26
  • The deterministic model has average degree approaching 4 and a maximal degree that grows with network size, while alternative deterministic versions yield other discrete distributions.The scale-free characterization relies on the cumulative behavior of the discrete degree spectrum rather than a continuous degree density.Source: C. A simple model of scale-free networks · p. 26

D. Scaling relations and cutoff

The section derives universal scaling relations for scale-free networks and shows that finite size imposes a degree cutoff that limits observable power laws.

D. Scaling relations and cutoff

  • γ = 1 + 1/β follows universally for scale-free networks without approximation, linking the degree-distribution and individual-vertex scaling exponents.The same relation identifies β with the exponent of Zipf’s law.Source: D. Scaling relations and cutoff · p. 27
  • kcut ∼ t^β = t^1/(γ−1) is the generic cutoff scale, with roughly one vertex expected above it.The cutoff can estimate γ from a network’s maximal degree.Source: D. Scaling relations and cutoff · p. 27
  • Power-law observations require at least 2–3 degree decades, imposing t > 10^2.5(γ−1) and making large γ difficult to detect.Finite size, initial-condition traces, and poor large-degree statistics jointly restrict empirical observation.Source: D. Scaling relations and cutoff · p. 27
  • Reported scale-free networks mostly lie within the finite-size region bounded by γ = 2, the size relation, and the World Wide Web’s approximate size limit.Fig. 24 compiles reported γ exponents and network sizes, while Table I documents the underlying cases and cautions about errors.Source: D. Scaling relations and cutoff · p. 27, Table I · p. 28, Figure 24 · p. 29
  • The degree distribution follows a scaling form with a rapidly decaying function that generates the finite-size cutoff.The derivation assumes stationary scaling behavior for the degree distribution and average degree.Source: D. Scaling relations and cutoff · pp. 26–27

E. Continuum approach

The continuum approach converts growth equations into tractable differential equations that reproduce key scale-free exponents. Generalized growth models show how random linking, preferential linking, rewiring, and directed correlations shape network structure.

E. Continuum approach

  • The continuum approximation gives exact exponents for the BA model and describes main growth features across many evolving-network models.Its δ-function ansatz differs from exact master-equation solutions but works effectively for exponential and scale-free networks.Source: E. Continuum approach · p. 30
  • For the BA model, β = 1/2 and γ = 3 follow from the continuum equations and the relation γ = 1 + 1/β.The model’s preferential-linking rule distributes new edges proportionally to vertex degree.Source: E. Continuum approach · p. 30

F. More complex models and estimates for the WWW

  • Adding randomly distributed edges preserves power-law degree distributions but increases γi, which can range between 2 and infinity.The generalized directed model combines random and preferential channels for incoming and outgoing links.Source: Figure 25 · p. 30, F. More complex models and estimates… · pp. 31–32, Figure 26 · p. 32
  • The WWW estimates give γi − 2 ∼ 10−1 versus observed 0.1 and γo − 2 ∼ 1 versus observed 0.7, while many unknown parameters limit precision.The authors characterize these as scale estimates rather than complete accounts of the real linking process.Source: F. More complex models and estimates… · pp. 31–32
  • Creating old-vertex connections yields 2 < γ < 3, whereas directed growth produces correlated in- and out-degrees rather than P(ki)P(ko).The joint distribution can differ substantially from the product of marginal degree distributions.Source: F. More complex models and estimates… · pp. 32–33
  • Rewiring lowers γ as preferential rewiring increases, but sufficiently high rewiring changes the degree distribution from a power law to an exponential.The rewiring model assumes the number of rewirings is small enough to avoid bare vertices.Source: F. More complex models and estimates… · pp. 32–33

G. Types of preference providing scale-free networks

Scale-free networks arise under several preference mechanisms, not only pure preferential linking. The resulting exponent depends on fitness, attractiveness, and aging, with aging producing distinct network structures.

G. Types of preference providing scale-free networks

  • Linear asymptotic preference is necessary for power-law degree distributions, while nonlinear ky preference fails when y ≠ 1.Fitness G and additional attractiveness A modify attachment probabilities and scaling exponents.Source: G. Types of preference providing… · p. 33
  • For aging preference G(s,t) = (t−s)^−α, negative α favors oldest vertices, whereas large α drives the network toward a chain structure.The aging exponent may take any real value while preserving scale-free behavior under the stated power-law form.Source: G. Types of preference providing… · p. 34, Figure 29 · p. 34
  • The aging model yields 0 < β < 1 and 2 < γ < infinity, with analytical and simulation results shown across α.Figures 30 and 31 compare the calculated exponents with simulations.Source: G. Types of preference providing… · p. 34, Figure 30 · p. 34, Figure 31 · p. 35
  • A uniformly distributed fitness produces γ = 2.255..., smaller than γ = 3 for the homogeneous BA model.The exponent depends on the fitness distribution P(G).Source: G. Types of preference providing… · p. 35
  • Most preferential-linking models produce “the oldest is the richest,” although fitness fluctuations broaden individual-vertex degree distributions and can obscure this pattern.The authors note that vertex death, division, or attachment cessation can alter age–degree behavior.Source: G. Types of preference providing… · p. 35

H. “Condensation” of edges

A sufficiently fit vertex can capture a finite fraction of edges, altering scaling exponents, while growth also creates degree correlations absent from equilibrium random graphs. These correlations shape neighbor-degree statistics and component-size distributions.

H. “Condensation” of edges

  • For g > gc, a single strong vertex captures a finite fraction of edges, producing an edge-condensation phase that remains scale-free while γ increases with g.The condensed fraction is independent of initial conditions in the long-time limit, and the strong vertex separates from all other vertices in in-degree.Source: H. “Condensation” of edges · pp. 36–37
  • The condensation threshold is gc = γ0 −1, and above it the strongest vertex grows linearly with time while capturing a macroscopic edge fraction.The threshold follows from comparing the strong vertex's growth with the homogeneous-network exponents β0 and γ0.Source: H. “Condensation” of edges · p. 36
  • The condensation state is approached by power-law relaxation, whose exponent vanishes at g = gc, evoking critical relaxation.The large-network final state is independent of initial conditions, but this asymptotic behavior is restricted to sufficiently large networks.Source: H. “Condensation” of edges · p. 37
  • With randomly mixed fitness values 1 and g, the threshold is smeared and condensation disappears, unlike the single-strong-vertex case.The corresponding exponents are defined separately for weak and strong components, whose behavior changes with the fraction p of strong vertices.Source: H. “Condensation” of edges · p. 37, Figure 34 · p. 37

I. Correlations and distribution of edges over network

  • Growing networks have correlated neighboring degrees because parent–child asymmetry breaks time-reversal symmetry, even without preferential linking.The joint degree probability does not factorize, distinguishing these networks from equilibrium graphs with statistically independent vertices.Source: §I · pp. 38–39
  • For γ < 3, nearest-neighbor degree follows knn(k) ∝ k−(3−γ) at small k and becomes logarithm-like at larger k.Adding preferential connections between old vertices can remove the power-law singularity as their number increases.Source: §I · p. 39
  • Citation-graph in-component sizes scale as t/s^2 for large s when the preference exponent y does not exceed 1, while typical out-components are of order ln t.The logarithmic out-component scale also holds across scale-free citation graphs with y ≤ 1.Source: §I · p. 39

J. Accelerated growth of networks

Accelerated edge input produces scale-free networks with stationary or non-stationary degree distributions depending on how attractiveness and edge flow grow. A word-web model shows that preferential attachment plus links among old vertices reproduces the observed distribution without fitting.

J. Accelerated growth of networks

  • Accelerated growth can yield stationary degree distributions with γ < 2 or non-stationary distributions with γ > 2, depending on the growth model.For power-law edge input, the resulting cutoff and scaling exponents depend on the relation between the degree-distribution exponent and the acceleration exponent.Source: J. Accelerated growth of networks · pp. 39–40
  • When additional attractiveness is constant, β = 1+a, γ = 1+1/(1+a), and the degree distribution is stationary apart from its time-dependent cutoff.For edge input proportional to t, this gives γ = 3/2.Source: J. Accelerated growth of networks · p. 40
  • When additional attractiveness grows with time, the degree distribution is non-stationary with γ > 2, and the scaling regime requires Ba < 1.The model gives β = (1 − Ba)/(1 + B), δ = a, and z = a(1 + B)/(1 − Ba).Source: J. Accelerated growth of networks · p. 40, Figure 35 · p. 40
  • Copying ancestor-neighbor connections produces effective linear preferential attachment and switches between stationary and non-stationary regimes at p = 1/2.For p < 1/2, γ = 1 + 1/p > 3; for p > 1/2, γ = 1 + 1/(1 − p) > 3 and the distribution is non-stationary.Source: J. Accelerated growth of networks · p. 40
  • The word-web model adds one preferentially attached word and ct preferentially linked edges among old words, yielding a stationary long-time exponent γ = 3/2.The model combines new-word attachment proportional to degree with old-word links weighted by kµkν.Source: J. Accelerated growth of networks · p. 41
  • The word-web degree distribution has a crossover near kcross ≈ 5 × 10^3, with a stationary low-degree region and a non-stationary high-degree tail.The crossover moves toward larger degrees as the network grows, while the number of words above it remains approximately constant.Source: J. Accelerated growth of networks · pp. 41–42
  • Using measured word-web parameters without fitting gives excellent agreement with the empirical distribution, including the crossover and cutoff positions.The main deviations occur for k < 10, where the continuum approximation and construction-dependent empirical points are not reliable.Source: J. Accelerated growth of networks · p. 41
  • The model implies that the language core remains approximately constant in size, of order 10^3–5,000 words, as the network evolves.This follows because the number of words above the moving crossover does not change.Source: J. Accelerated growth of networks · pp. 41–42

K. Decaying networks

This section examines how decay, edge deletion, and related structural mechanisms shape evolving and equilibrium network topology. It develops percolation criteria and giant-component properties while addressing scale-free behavior, spectral and geometric signatures, degree distributions, and modeling limitations.

K. Decaying networks

  • Random edge removal increases γ_i monotonically with c/m, reaches γ_i = ∞ on γ_0 = (c/m) + 1/(c/m), and can eliminate scale-free behavior or leave uncoupled clusters.Permanent deletion of the highest-degree vertices likewise destroys the network’s scaling behavior.Source: K. Decaying networks · p. 42, Figure 37 · p. 42

L. Eigenvalue spectrum of the adjacency matrix

  • The Barabási–Albert network’s eigenvalue spectrum is far from semicircular and has a power-law tail, unlike classical random graphs.The comparison concerns the growing scale-free network with γ = 3 and parallels observations for the Internet.Source: L. Eigenvalue spectrum of the… · p. 42

M. Scale-free trees

  • Equilibrium scale-free trees can have 2 < γ < ∞, cutoff k_cut ∼ N^1/(γ−1), and power-law distances ℓ ∝ N^1/d_H rather than logarithmic distances.Their fractal dimension is d_H = 2 for γ > 3 and d_H = (γ − 1)/(γ − 2) for 2 < γ < 3.Source: M. Scale-free trees · p. 43

X. NON-SCALE-FREE NETWORKS WITH PREFERENTIAL LINKING

  • Preferential linking proportional to k^y is scale-free only in restricted cases; y > 1 concentrates links on the oldest vertex, while partial copying produces non-scale-free multifractal in-degree distributions.For y > 2, all but finitely many vertices connect to the oldest vertex, and the multifractal moments obey M_n(t) ∼ t^τ(n) with nonlinear τ(n).Source: §X · pp. 43–44

XI. PERCOLATION ON NETWORKS

  • On networks, percolation is identified with giant-component emergence, which can occur by changing the degree distribution without deleting vertices or edges.Equilibrium and evolving networks have different percolation behavior, and the equilibrium theory discussed here applies specifically to Molloy–Reed graphs.Source: §XI · p. 44

A. Theory of percolation on undirected equilibrium networks

  • A giant connected component emerges when z_2 > z_1, while the tree-based shortest-path estimate fails for γ < 3 because z_2 diverges.The criterion applies to large, statistically uncorrelated, tree-like equilibrium networks; for 2 < γ < 3, the approach gives only a rough lower estimate.Source: A. Theory of percolation on undirected… · p. 46
  • A giant connected component exists when Σ_{k≥3} k(k−2)P(k) > P(1), so dead ends determine whether the component can form, whereas isolated vertices do not.When P(1)=0, the condition reduces to positive probability for degrees k≥3, excluding the special case P(2)=1.Source: A. Theory of percolation on undirected… · p. 46
  • Absence of dead ends, P(1)=0, yields W=1; power-law distributions with γ≤2 also yield W=1 formally, but violate the tree ansatz because their first moment diverges.If P(1)>0, usually W<1; for γ≤2, the number of edges grows faster than the number of vertices as network size increases.Source: A. Theory of percolation on undirected… · p. 47
  • For Erdős–Rényi networks, the giant component satisfies 1−W=e^(−z1W) and exists when the average degree exceeds one.The result follows from the Poisson degree distribution, which gives Φ(y)=e^{z1(y−1)}.Source: A. Theory of percolation on undirected… · p. 47
  • At the percolation threshold, the component-size distribution follows Ps(w)∼w^−3/2, while the probability for a vertex to belong to a size-w finite component follows P(w)∼w^−5/2.The exponent 3/2 is shared by reasonable degree distributions, and the stated scaling is valid only near the threshold.Source: A. Theory of percolation on undirected… · p. 47
  • Near the threshold, the largest component has size O(N^2/3) when no giant component exists, the second largest is O(ln N), and other components are O(ln N) or smaller when γ>2.The latter bound applies when a giant component exists and γ>2.Source: A. Theory of percolation on undirected… · p. 47
  • The theory extends percolation analysis to undirected bipartite graphs and predicts one-mode degree distributions from the two vertex-type degree distributions, matching empirical collaboration data closely.The prediction was checked using Fortune 1000 boards, movie actors, and physics collaborations; the Fortune 1000 co-director distribution was very close to empirical data.Source: A. Theory of percolation on undirected… · pp. 47–48

B. Percolation on directed equilibrium networks

The review develops exact percolation results for statistically uncorrelated directed equilibrium networks using joint in- and out-degree distributions, distinguishing their giant components and critical behavior.

B. Percolation on directed equilibrium networks

  • The probabilities x_c and y_c represent finite components reached against and along edge directions, respectively, and determine GIN and GOUT sizes.I = 1 − Φ(x_c, 1) and O = 1 − Φ(1, y_c).Source: B. Percolation on directed equilibrium… · p. 48
  • Exact equations determine the relative sizes of all giant components for arbitrary joint in- and out-degree distributions when vertices are statistically uncorrelated.The framework covers the GSCC, GWCC, GIN, and GOUT.Source: B. Percolation on directed equilibrium… · p. 48
  • When the joint degree distribution factorizes, the GSCC size simplifies to S = IO; otherwise, this factorization is impossible.At emergence, GIN, GOUT, and GSCC sizes simultaneously approach zero.Source: B. Percolation on directed equilibrium… · p. 48
  • Near the critical point, GIN and GOUT sizes vary linearly with the control parameter, whereas GSCC size varies quadratically.These variations are summarized schematically in Fig. 38.Source: B. Percolation on directed equilibrium… · p. 49, Figure 38 · p. 49
  • Applying the uncorrelated equilibrium theory to the WWW is limited because its growth produces strong vertex correlations absent from the model.A factorized approximation also predicts substantially unequal giant in- and out-components, unlike the nearly equal WWW components.Source: B. Percolation on directed equilibrium… · p. 49

C. Failures and attacks

The review contrasts random failures with targeted attacks in exponential and scale-free networks, showing that scale-free networks are far more vulnerable to intentional removal of high-degree vertices than to random damage.

C. Failures and attacks

  • The simulations compare real WWW and Internet networks, a γ = 3 Barabási–Albert model, and an exponential growing network after vertex removal.Failures remove randomly selected vertices, while attacks remove vertices with the highest degrees.Source: C. Failures and attacks · p. 49
  • Under intentional damage, scale-free networks show mean-field-like behavior: S(f) ∝ (f_c − f) near the threshold and average shortest paths diverge at f_c.The qualitative attack effect is reported as similar across the four scale-free networks considered.Source: C. Failures and attacks · p. 50
  • For scale-free networks with γ ≤3, random removal has a percolation threshold as f →1, whereas intentional damage destroys the giant component at an anomalously low threshold of several percent.Intentional damage rapidly increases average shortest paths and drives S to zero at f_c.Source: C. Failures and attacks · p. 50
  • Random damage has a far weaker effect on scale-free networks than intentional attacks, with shortest paths and giant strongly connected components changing slowly under random removal.Scale-free networks may require deletion of practically all vertices to eliminate the giant connected component through random damage.Source: C. Failures and attacks · p. 50
  • The review attributes attack sensitivity to the structural role of high-degree vertices, while treating resilience to failures as requiring further explanation.Comparable observations were reported for metabolic, protein, and food-web networks.Source: C. Failures and attacks · p. 50

D. Resilience against random breakdowns

The review develops percolation criteria for random failures and intentional attacks in evolving networks, showing contrasting resilience that depends on degree structure, network size, and damage targeting.

D. Resilience against random breakdowns

  • Random site and bond percolation share the threshold condition p z2 > z1, expressed using the virgin network’s first- and second-neighbor averages.The degree distribution and moments must refer to the undamaged network.Source: D. Resilience against random breakdowns · p. 51
  • Divergent second moments make the infinite-network threshold pc vanish, so scale-free networks with γ ≤3 require removal of practically all vertices to eliminate their giant component.The same mechanism can produce super-resilience in networks with copied or inherited connections.Source: D. Resilience against random breakdowns · p. 52
  • Finite networks retain thresholds despite the infinite-size limit: for γ = 2.5, pc is approximately 10^-2 at N = 10^6 and 10^-3 at N = 10^9.For γ = 3 and k0 = 3, pc decreases from approximately 0.07 at N = 10^4 to 0.03 at N = 10^9.Source: D. Resilience against random breakdowns · p. 52, Figure 40 · p. 52
  • The random-damage analysis is derived for equilibrium networks and appears to describe instant damage in growing networks, but not permanent damage.This limits the direct analytical scope of the results.Source: D. Resilience against random breakdowns · p. 52

E. Intentional damage

  • For networks with P(0) = 0 and power-law degree distributions, intentional removal of highest-degree vertices yields fc = 2.3 × 10^-2, 1.0 × 10^-2, and 0.2 × 10^-2 for γ = 2.4, 2.7, and 3.0, respectively.fc > 0 only for 2 < γ < 3.479..., and the result is sensitive to the small-k form of P(k) and the number of dead ends.Source: E. Intentional damage · pp. 53–54, Figure 41 · p. 54
  • Intentional attacks remove the highest-degree vertices through a degree-dependent occupation rule, yielding a generalized Molloy–Reed criterion for the percolation threshold.The exact treatment is equivalent to approaches that separately account for deleted vertices and their incident edges.Source: E. Intentional damage · p. 53

F. Disease spread within networks

Disease spread depends strongly on network degree distributions, while growing networks exhibit anomalous percolation behavior that differs from equilibrium mean-field expectations.

F. Disease spread within networks

  • For non-scale-free networks, disease prevalence vanishes below a nonzero epidemic threshold and becomes endemic above it.Above threshold, prevalence grows linearly near λc.Source: F. Disease spread within networks · p. 54
  • In infinite scale-free networks with γ ≤3, the epidemic threshold is absent because the second degree moment diverges.The same fat-tailed degree distributions produce resilience to random damage but sensitivity to infection spread.Source: F. Disease spread within networks · p. 55
  • Finite networks retain an effective epidemic threshold, which may be large enough to matter unless γ is close to 2 or below.The infinite-network result therefore does not directly determine epidemic behavior in real finite networks.Source: F. Disease spread within networks · p. 55
  • Targeted immunization of highly connected vertices is more effective than random immunization for restoring epidemic control in scale-free networks.Random immunization cannot restore the epidemic threshold in these networks.Source: F. Disease spread within networks · p. 55

G. Anomalous percolation on growing networks

  • Growing networks undergo an infinite-order percolation transition at bc = 1/8, with giant-component size W vanishing nonlinearly rather than linearly.The transition cannot be described by effective-medium theory, and all derivatives of W(b) vanish at the threshold.Source: G. Anomalous percolation on growing… · p. 56, Figure 42 · p. 56
  • At the growing-network threshold, finite-component size jumps from 2 below to 4 above, rather than diverging as in standard percolation.The anomalous transition is not accompanied by an anomaly in the degree distribution.Source: G. Anomalous percolation on growing… · p. 56
  • Finite-component distributions have a power-law tail throughout the no-giant-component phase and a cutoff above the transition.At threshold, P(s) ∝ [s ln s]^-2; above threshold, the cutoff scales as sc ∝ 1/W.Source: G. Anomalous percolation on growing… · p. 56
  • Effective preferential growth of large components explains why the no-giant-component phase is critical, whereas merger into the giant component makes the supercritical phase exponential.New edges favor mergers involving large components even when attached to randomly chosen vertices.Source: G. Anomalous percolation on growing… · pp. 56–57

XII. GROWTH OF NETWORKS AND SELF-ORGANIZED CRITICALITY

The paper links growing-network models to self-organized criticality, preferential-allocation processes, and multiplicative stochastic dynamics. These connections explain how scale-free distributions arise and clarify both the scope and limits of the reviewed models.

XII. GROWTH OF NETWORKS AND SELF-ORGANIZED CRITICALITY

  • Changing growth parameters can move networks away from scale-free structure, linking network evolution to self-organized criticality.The review connects these processes with broader non-equilibrium phenomena.Source: §XII · p. 57

A. Linking with sand-pile problems

  • Preferential-linking models map onto a particle-allocation process in which particles are distributed among newly added boxes according to occupancy-dependent rules.Boxes represent vertices and particles represent edges, providing a sand-pile-like formulation.Source: A. Linking with sand-pile problems · p. 57

B. Preferential linking and the Simon model

  • The Simon model produces power-law family-size distributions because new individuals join existing families with probability proportional to family size.Its exponent is γ = 1 + 1/(1 −p).Source: B. Preferential linking and the Simon… · pp. 57–58
  • The Simon model shares preferential-allocation behavior with network growth but does not by itself address full network topology.It adds individuals one at a time, whereas the reviewed network models add one vertex at each step.Source: B. Preferential linking and the Simon… · p. 58

C. Multiplicative stochastic models and the generalized Lotka-Volterra equation

  • Preferential linking can also be viewed as a multiplicative stochastic process because a vertex’s degree increase is proportional to its current degree.This connects network growth to models used for wealth distributions in econophysics and evolutionary biology.Source: C. Multiplicative stochastic models… · p. 58
  • The generalized Lotka-Volterra formulation yields stationary power-law distributions with exponent γ = 2 + A/D and a long-time fixed average wealth.The resulting distribution is independent of B and c(w,t).Source: C. Multiplicative stochastic models… · p. 58

XIII. CONCLUDING REMARKS

  • Preferential linking generates long-tailed degree distributions and helps self-organize growing networks into scale-free structures.These networks can be highly resilient to random damage but permit disease spread, while equilibrium-network assumptions fail for growing networks.Source: §XIII · pp. 58–59
  • The reviewed models remain schematic and qualitative for real networks, and the review omits several recent topics and results.The authors specifically note that the models address only particular phenomena in real networks.Source: §XIII · pp. 58–59
Loading cond-mat/0106144v2…