Network Formation: How Preferential Attachment Builds a Scale-Free World

Two ways to grow a network

The classic random graph, formalised by Paul Erdős and Alfréd Rényi in 1959, connects a fixed set of nodes with edges chosen uniformly at random. Its degree distribution is a narrow Poisson bump around the average — almost every node has roughly the same number of connections, and hubs simply do not appear. Real networks look nothing like this. Airports, citation graphs, the World Wide Web and social platforms all have a small number of nodes with enormous numbers of connections and a huge majority with very few. Albert-László Barabási and Réka Albert showed in 1999 that the missing ingredient was not randomness but growth combined with preferential attachment.

The rule: connect to the well-connected

The Barabási-Albert (BA) model starts with a small connected core of nodes and adds new nodes one at a time. Each new node brings m new edges, and — this is the entire mechanism — the probability that a new edge attaches to an existing node i is proportional to that node's current degree k_i, not chosen uniformly at random:

P(attach to node i) = k_i / Σ_j k_j

each new node adds m edges chosen by this rule
→ nodes that already have many links are disproportionately
  likely to gain the next one — a literal rich-get-richer process

This models an everyday reality: a new webpage is easier to find and more likely to link to a page that is already widely linked to; a new academic paper is more likely to cite a paper that is already famous, precisely because famous papers are how researchers find the literature in the first place; a new social media account is more likely to follow accounts that already have large followings, because visibility itself grows with degree. First-mover advantage compounds — nodes that join early have more time to accumulate connections, which is why the very first hubs in a growing network tend to stay the largest.

A power law, not a bell curve

The consequence of this simple rule is a degree distribution that follows a power law, P(k) ~ k^-γ, with the original BA model producing an exponent of γ = 3. A power-law distribution has no characteristic scale: there is no "typical" node degree the way there is a typical height in a human population, which is exactly why these are called scale-free networks. Practically, this means a small number of hubs — sometimes just a fraction of a percent of all nodes — account for a large share of all connections in the network, a pattern confirmed empirically in web hyperlink graphs, airline route maps, protein-interaction networks and academic citation graphs.

Robust to random failure, fragile to targeted attack

This structure produces a famous and somewhat counterintuitive robustness property, studied by Réka Albert, Hawoong Jeong and Barabási in 2000. Remove nodes at random from a scale-free network and it barely notices — because the overwhelming majority of nodes have low degree, a random deletion is very unlikely to hit a hub, and the network stays connected across a wide range of failure rates. But remove the small number of highest-degree hubs deliberately, and the network fragments after just a few removals, since those hubs were carrying a disproportionate share of all the paths through the network. This asymmetry — robust to accidents, vulnerable to targeted attack — matters directly for internet infrastructure resilience, epidemic control (vaccinating hubs first is far more effective than vaccinating at random) and cybersecurity.

Beyond the basic model

Preferential attachment on degree alone predicts that the oldest nodes always end up the biggest, which is not always true in practice — a genuinely superior newcomer can still overtake older, better-connected incumbents. The fitness model extension, introduced by Ginestra Bianconi and Barabási, multiplies the attachment probability by a node-specific fitness factor, allowing a late but highly attractive node to win disproportionately large market share even against much older competitors — sometimes even producing a winner-take-all outcome similar to Bose-Einstein condensation in the network's degree distribution.

Frequently asked questions

Try it live

Everything above runs in your browser — open Network Formation and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.