The foundations of networks
A network is a set of things and the connections between them. Friendships, power lines, neurons, web pages and routers have nothing in common as substances — and a great deal in common as patterns. The science of networks is the study of what follows from the pattern alone.
Three choices made the internet. Cut every message into packets that find their own way, proposed by Paul Baran in the early 1960s, set out in full in his reports of 1964, and named by Donald Davies in 1965. Stack the work in layers, so that any application can run over any wire — the design Vinton Cerf and Robert Kahn published in 1974 as a single protocol, divided into the separate layers TCP and IP in 1978. And keep the middle simple, leaving the intelligence at the edges: the end-to-end argument of Saltzer, Reed and Clark, first given in 1981 and published in its familiar form in 1984. The result is a network of tens of thousands of independently run networks.
A network with a few very well-connected hubs shrugs off random failures, because most nodes matter little, and is badly hurt by the loss of the hubs themselves. Réka Albert, Hawoong Jeong and Albert-László Barabási showed the asymmetry in 2000. Failures can also travel: in August 2003 the loss of a few power lines in Ohio began a cascade that cut power to some fifty million people.
Diseases, rumours, software updates and bank failures all spread along links. The classical epidemic model of Kermack and McKendrick (1927) assumes everyone mixes evenly and predicts a threshold below which an outbreak dies away. Romualdo Pastor-Satorras and Alessandro Vespignani showed in 2001 that with hubs in the network, that threshold can all but disappear.
In many real networks most nodes have a handful of links and a few have an enormous number. One cause is growth with preference: newcomers attach to nodes that are already popular, so the rich get richer. Derek de Solla Price found the pattern in scientific citations in 1965 and gave the mechanism in 1976; Barabási and Albert applied it to networks in general, and named it, in 1999. How common such “scale-free” networks really are was questioned by Anna Broido and Aaron Clauset in 2019.
In Stanley Milgram’s experiment of 1967, the letters that reached their target did so in about six steps — though most never arrived. Duncan Watts and Steven Strogatz explained it in 1998: a network can be tightly clustered, like a village, and still have short paths, provided a small fraction of its links are long-range shortcuts. Mark Granovetter had argued in 1973 that those weak, distant ties are the ones that carry news.
Once a system is drawn as a network, questions become calculations: how many links a node has, the shortest route between two nodes (Edsger Dijkstra’s algorithm, 1959), how much a node sits between others. The ranking method that Larry Page and Sergey Brin described in 1998 ranked a web page by the pattern of links pointing to it.
In the 1730s Leonhard Euler took up the question of whether one could walk through Königsberg crossing each of its seven bridges exactly once. He saw that distances and shapes were irrelevant: only which land masses the bridges joined mattered, and the answer was no. That step — keep the connections, discard everything else — is the foundation of the subject.
Read from the bottom up. The first six ideas are about networks of any kind. The seventh is engineering: what it took to build a worldwide network with nobody in charge of it.