mathematics//graph theory//scale-free network

A scale-free network is a network whose node degrees follow a heavy-tailed, roughly power-law distribution, so that most nodes have a few links and a few hubs have a great many, and its practical importance is a lopsided robustness: it survives random failures well and collapses quickly when the hubs are attacked. Albert, Jeong and Barabási showed this in 2000 on maps of the internet and the web: removing random nodes barely changed connectivity, while removing the few most connected ones broke the network into pieces.

A scale-free network is a network whose node degrees follow a heavy-tailed, roughly power-law distribution, so that most nodes have a few links and a few hubs have a great many, and its practical importance is a lopsided robustness: it survives random failures well and collapses quickly when the hubs are attacked. Albert, Jeong and Barabási showed this in 2000 on maps of the internet and the web: removing random nodes barely changed connectivity, while removing the few most connected ones broke the network into pieces.

The reason is counting. A random failure almost always hits one of the many poorly connected nodes, whose loss changes little; a targeted attack goes straight for the hubs, through which most shortest paths run. The degree distribution is P(k)∝k−γP(k)\propto k^{-\gamma}P(k)∝k−γ, typically with γ\gammaγ between 2 and 3, a heavy-tailed distribution with no typical degree, hence the name.

A single map server is a hub, whether or not the architecture diagram draws it as one.

A fleet in which every robot pulls its map, task list or clock from one service has the scale-free weakness built in: random robot failures are absorbed, and the loss of that one service stops everything (single point of failure).

Hubs also speed spreading. Information, epidemics and overloads cross a hub-dominated network in few hops, which helps a gossip protocol and hurts a power grid during a cascading failure.

The power-law label is often overstated, since many networks called scale-free fit other heavy-tailed distributions just as well. The engineering lesson does not depend on the exact exponent; it depends on whether a few nodes carry a disproportionate share of the links or the traffic.

Defending such a network means removing the hubs' privilege: replicate the central services (state machine replication), give agents a degraded mode that works without them, and protect the hubs first, since an attacker will look for them.

It belongs to the study of complex system behaviour, where coupling explains the size of a failure better than any single component does; the graph vocabulary is in graph theory.