EVOPEDIA

← all systems · see it in The System

Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea)

'a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems' (Complex network). 'Systems as diverse as genetic networks or the world wide web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution.' (Barabási and Albert 1999)

Properties published scienceour proposal

Sourced fields, and our own readings.

aliasescomplex (scale-free) network
born at1998-1999 for complex networks as a field (Watts and Strogatz 1998; Barabási and Albert 1999); 'since 2000' as a research area; precursors 1925 (Yule), 1955 (Simon), 1959 (Erdős and Rényi), 1976 (Price)
born precisionyear
boundaryInside: the network structure as defined and held: vertices and links, the degree distribution, clustering and path length, the growth and attachment rules that make heavy tails (preferential attachment, its nonlinear, aging, cost and fitness forms), the phases of a growing network (scale-free state, winner-takes-all gel, Bose-Einstein condensate, giant cluster) and its robustness and fragility. Outside: the real systems it is used to read (metabolism, food webs, nervous systems, the Web, the Internet, citations, actors, power grids), the scientists, data indexes and literature that hold it, and the other theories it maps onto (Simon's model, the Bose gas, percolation, causal sets).
nested levelAn idea of statistical physics and network science held by sys:science (rung 11): a graph with non-trivial topology, set against the simple networks (lattices, Erdős-Rényi random graphs); its projected content walked as a model (representation: true), read in living systems (rung 6 metabolism, food webs, nervous systems) and in human records and technology (rungs 11-12).
representationTrue
scalesocial

Measures (17) published science

actor collaboration degree exponent2.3 ± 0.1 gamma
World Wide Web in-link degree exponent2.1 ± 0.1 gamma
World Wide Web size (1999)over 800 million vertices (documents)
western US power grid4941 vertices; exponent about 4 vertices; gamma
citation network degree exponent3 gamma
observed exponent range2.1 to 4 gamma
Barabasi-Albert model exponent3 (analytic); 2.9 ± 0.1 (simulation) gamma
characteristic clock: degree growth of a vertexk_i(t) = m (t/t_i)^0.5 links vs time steps since the vertex joined
attack fragmentation threshold (scale-free, gamma near 2)about 0.03 fraction of highest-degree nodes removed
Internet domain-level clustering coefficient0.18 to 0.3 C
Internet router-level map (Govindan 2000)about 150,000 router interfaces
metabolic networks compared43 organisms (all three domains of life)
network data sets tested for scale-free structure928 data sets (ICON)
share of data sets strongly or strongest scale-free10% (Strong); 4% (Strongest) percent of data sets
share of data sets with exponent below 234% percent of data sets
small-world onset in the Watts-Strogatz modelp* ~ 1/N rewiring probability
C. elegans neural network size (BA note 12)306 vertices

Open contentions (1) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (4)

Sits inside / holds (2)

Trades with (valence) (8)

expressed by (6)

floor filled by (21)

represents (8)

Kinds (9)

Notes published science

Layers

The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.

complex network (own: vertices, links and their statistics; projected model)

  1. L1: Vertices and links: 'vertices are the elements of the system and edges represent the interactions between them'; directed (web links, citations) or undirected (actors)
  2. L2: Degree distribution P(k): Poisson in Erdős-Rényi graphs, peaked in Watts-Strogatz, power law k^-gamma (gamma 2.1-4) in many real networks; three classes: scale-free, broad-scale, single-scale
  3. L3: Clustering and short paths: high clustering coefficient with distance growing as log N (small worlds); a few rewired long-range links shrink a lattice
  4. L4: Growth and attachment rules: new vertices added; attachment probability Pi(k) = k / sum k_j; kernels sublinear, linear, superlinear; aging, cost and capacity constraints; fitness
  5. L5: Phases of the whole: the stationary scale-free state; a giant cluster once <k> > 1; winner-takes-all gel (superlinear); Bose-Einstein condensate (fittest node keeps a finite share); fit-get-rich
  6. L6: Robustness and fragility: tolerant of random node failures, vulnerable when hubs are targeted; fragmentation at a critical fraction (about 0.03 under attack for gamma near 2)

metabolic networks read across the three domains of life (projected model on the metabolite pool)

  1. L1: Substrates as nodes, reactions as links (ATP, ADP and water among the most connected), from a pathway database of 43 organisms
  2. L2: Scale-free in every organism read, in all three domains of life
  3. L3: The same diameter (shortest biochemical pathway averaged over substrate pairs) in all 43 organisms, whatever their number of substrates
  4. L4: Robust and error tolerant: hubs link the rest; simple organisms persist despite drastic interventions; linked to growth with preferential attachment in evolution

networks read in human records and technology: citations, the Web, the Internet, actors, power grids (projected model on the written record)

  1. L1: Documents and links: web pages and hyperlinks (over 800 million vertices, 1999); papers and citations; actors cast together; generators and transmission lines (4941 vertices); routers (about 150,000 interfaces)
  2. L2: Heavy tails: gamma 2.1 (Web in-links), 2.3 (actors), 3 (citations), about 4 (power grid); Internet clustering 0.18-0.3
  3. L3: Growth: the Web grows exponentially by new pages, the literature by new papers, the actor network by new actors
  4. L4: Preferential linking: new pages link to well-known documents, new papers cite much-cited ones; airports capped by space and time

the complex network as held by science (mental representation)

  1. L1: Papers and data: Yule 1925, Simon 1955, Erdős and Rényi 1959-61, Price 1976, Watts and Strogatz 1998, Barabási and Albert 1999, Albert and Barabási 2002 review, Broido and Clauset 2019; data from computerised acquisition and the Index of Complex Networks (ICON)
  2. L2: Encoding: three robust measures (average path length, clustering coefficient, degree distribution); definitions of 'scale-free' from Super-Weak to Strongest; heavy-tailed vs power-law
  3. L3: Mappings: Simon's model (exact), the Bose gas, percolation theory, gelation, causal sets of de Sitter spacetime
  4. L4: Dispute: 'rare' (strongly scale-free in 4% of 928 data sets; log-normals fit as well) vs 'everywhere' (heavy tails, universality in the infinite-size limit); keep both schools

Who fills each layer

Sources (18) published science

Barabási, A.-L. and Albert, R. (1999) Emergence of scaling in random networks. Science 286, 509; doi:10.1126/science.286.5439.509 (cross-domain sighting); arXiv:cond-mat/9910332 (full text read)
Albert and Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002), doi:10.1103/RevModPhys.74.47 (arXiv cond-mat/0106096) (behind its links)
Krapivsky, Redner and Leyvraz, Connectivity of Growing Random Networks, PRL 85 (2000), doi:10.1103/PhysRevLett.85.4629 (arXiv cond-mat/0005139) (behind its links)
Jeong, Tombor, Albert, Oltvai and Barabási, The large-scale organization of metabolic networks, Nature 407 (2000), doi:10.1038/35036627 (arXiv cond-mat/0010278) (behind its links)
Complex network (Wikipedia), via the Wikimedia Enterprise snapshot 2026-11-01 (behind its links)
Broido and Clauset, Scale-free networks are rare, Nat. Commun. 10 (2019), doi:10.1038/s41467-019-08746-5 (PMC6399239) (behind its links)
Witthaut D, Hellmann F, Kurths J, Kettemann S, Meyer-Ortmanns H, Timme M (2022). Collective nonlinear dynamics and self-organization in decentralized power grids. Reviews of Modern Physics 94:015005. doi:10.1103/RevModPhys.94.015005 (authors' institutional copy) (behind its links)
Bianconi and Barabási, Bose-Einstein condensation in complex networks, PRL 86 (2001), doi:10.1103/PhysRevLett.86.5632 (arXiv cond-mat/0011224) (behind its links)
Krioukov, Kitsak, Sinkovits, Rideout, Meyer and Boguna, Network cosmology, Sci. Rep. 2 (2012), doi:10.1038/srep00793 (PMC3499772) (behind its links)
Preferential attachment (Wikipedia), via the Wikimedia Enterprise snapshot 2026-11-01 (behind its links)
Watts DJ (2002) A simple model of global cascades on random networks. PNAS 99:5766-5771, doi:10.1073/pnas.082090499 (behind its links)
Pastor-Satorras, Vazquez and Vespignani, Dynamical and correlation properties of the Internet, PRL 87, 2001 (arXiv cond-mat/0105161) (behind its links)
Mathieson and Scally, What is ancestry?, PLoS Genet. 16 (2020), doi:10.1371/journal.pgen.1008624 (PMC7082057) (behind its links)
Apicella CL, Marlowe FW, Fowler JH, Christakis NA. 2012. Social networks and cooperation in hunter-gatherers. Nature 481:497-501. doi:10.1038/nature10736 (PMC3340565, author manuscript) (behind its links)
Barabási A-L, Albert R. Emergence of scaling in random networks. Science 286:509 (1999); arXiv:cond-mat/9910332 (behind its links)
Small-world network (Wikipedia), via the Wikimedia Enterprise snapshot 2026-11-01 (behind its links)
Holme, Rare and everywhere: Perspectives on scale-free networks, Nat. Commun. 10 (2019), doi:10.1038/s41467-019-09038-8 (PMC6399274) (behind its links)
Amaral, Scala, Barthélémy and Stanley, Classes of small-world networks, PNAS 97 (2000), doi:10.1073/pnas.200327197 (arXiv cond-mat/0001458) (behind its links)