← 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.
| aliases | complex (scale-free) network |
| born at | 1998-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 precision | year |
| boundary | Inside: 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 level | An 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). |
| representation | True |
| scale | social |
Measures (17) published science
| actor collaboration degree exponent | 2.3 ± 0.1 gamma |
| World Wide Web in-link degree exponent | 2.1 ± 0.1 gamma |
| World Wide Web size (1999) | over 800 million vertices (documents) |
| western US power grid | 4941 vertices; exponent about 4 vertices; gamma |
| citation network degree exponent | 3 gamma |
| observed exponent range | 2.1 to 4 gamma |
| Barabasi-Albert model exponent | 3 (analytic); 2.9 ± 0.1 (simulation) gamma |
| characteristic clock: degree growth of a vertex | k_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 coefficient | 0.18 to 0.3 C |
| Internet router-level map (Govindan 2000) | about 150,000 router interfaces |
| metabolic networks compared | 43 organisms (all three domains of life) |
| network data sets tested for scale-free structure | 928 data sets (ICON) |
| share of data sets strongly or strongest scale-free | 10% (Strong); 4% (Strongest) percent of data sets |
| share of data sets with exponent below 2 | 34% percent of data sets |
| small-world onset in the Watts-Strogatz model | p* ~ 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.
- C-392 Are 'scale-free' networks rare or everywhere?
booked: The map keeps both: strict scale-free structure is rare across 928 data sets, while heavy-tailed connections are very common.
the other reading: one school wins: power laws are a universal property of growing networks / or power laws are a poor model of most real degree distributions
Partners and parts published science
Built from / builds (4)
- Vertices (nodes): the elements of the system
- Links (edges): the interactions between elements
- Hubs: the few highly connected vertices
- Competition over how real networks' degrees are described (scale-free power law against heavy-tailed alternatives such as the log-normal)
Sits inside / holds (2)
Trades with (valence) (8)
- Social contagion via sys:complex-network · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) gain
- Internet via sys:written-record · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) gain
- Science (as a human social and cultural system) via sys:written-record · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) gain
- Causal set (causet; hypothetical discrete spacetime) via sys:spacetime · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) gain
- Bose-Einstein condensate via sys:mental-representation · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) gain
- genealogy (descent as a medium) via sys:complex-network · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) gain
- Social structure via sys:human-society · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) even
- Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on via sys:written-record · Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) gain
expressed by (6)
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Interoperability/Transduction (Bridging)
- Mapping/Modeling
- Hypothesis Portfolio / Multiple Hypothesis Tracking
- Validation of Effectiveness
floor filled by (21)
- Metabolite pool (small molecules made, carried and turned over in a cell)
- Human (Homo sapiens)
- Science (as a human social and cultural system)
- Mental representation (beliefs, meanings, feelings and shared intentions)
- Internet
- Causal set (causet; hypothetical discrete spacetime)
- Bose-Einstein condensate
- Vertices (nodes): the elements of the system
- Links (edges): the interactions between elements
- Hubs: the few highly connected vertices
- Scale-free network
- Broad-scale (truncated scale-free) network
- Single-scale network
- Small-world network
- Random graph (Erdős-Rényi)
- Lattice graph
- Percolation
- Social network
- Electrical grid
- Social structure
- Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on
represents (8)
- Metabolite pool (small molecules made, carried and turned over in a cell)
- Nervous system
- Trophic network (food webs: who eats whom, from primary production through consumers to decomposers)
- Human (Homo sapiens)
- Internet
- Social network
- complex networks as held by science: a graph with non-trivial topology read in real systems (no rung 0-1 structure booked; readings at rung 6 and in causal sets tagged new:complex-network-physical-rea
- Electrical grid
Kinds (9)
- Scale-free network
- Broad-scale (truncated scale-free) network
- Single-scale network
- Small-world network
- Biological networks
- Social network
- Technological networks
- Information networks
- Transportation networks
Notes published science
- A growing network can undergo Bose-Einstein condensation: the fittest node keeps a finite share of all links forever, while everyone else's share thins to zero (Bianconi and Barabási 2001), which is the not-diluting-wins shape in a web of links.
- The oldest rich-get-richer model is about genealogy: Yule (1925) modelled genera gaining species in proportion to how many they already had.
- The causal structure of our accelerating universe, drawn as a graph, looks like the Internet: power-law degrees and strong clustering, with growth dynamics asymptotically the same (Krioukov et al. 2012, a hypothesised causal-set reading).
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)
- 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)
- 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
- 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
- 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
- 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
- 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)
- L1: Substrates as nodes, reactions as links (ATP, ADP and water among the most connected), from a pathway database of 43 organisms
- L2: Scale-free in every organism read, in all three domains of life
- L3: The same diameter (shortest biochemical pathway averaged over substrate pairs) in all 43 organisms, whatever their number of substrates
- 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)
- 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)
- L2: Heavy tails: gamma 2.1 (Web in-links), 2.3 (actors), 3 (citations), about 4 (power grid); Internet clustering 0.18-0.3
- L3: Growth: the Web grows exponentially by new pages, the literature by new papers, the actor network by new actors
- 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)
- 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)
- 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
- L3: Mappings: Simon's model (exact), the Bose gas, percolation theory, gelation, causal sets of de Sitter spacetime
- 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
- L1: Social contagion
- L2: Social contagion
- L3: Social contagion
- L5: Social contagion
Sources (18) published science
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)
Broido and Clauset, Scale-free networks are rare, Nat. Commun. 10 (2019), doi:10.1038/s41467-019-08746-5 (PMC6399239) (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)
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)