Scale-free network

A scale-free network is a graph whose degree distribution follows a power law: the probability that a node has degree k is proportional to k^−γ for some exponent γ typically between 2 and 3. Unlike random graphs with Poisson degree distributions, scale-free networks possess a small number of highly connected hub nodes alongside a vast majority of sparsely connected nodes.

This heterogeneity makes scale-free networks robust to random failure but vulnerable to targeted attack on hub nodes, a pattern observed in protein interaction networks and citation networks. The generative mechanism for scale-free topology is preferential attachment, in which new nodes preferentially connect to already well-connected nodes.