  One of the best-known models in network science is preferential attachment.
In this model, the probability of attaching to a node depends on the degree of
all nodes in the population, and thus depends on global information. In many
biological, physical, and social systems, however, interactions between
individuals depend only on local information. Here, we investigate a truly
local model of network formation, based on the idea of a friend of a friend,
with the following rule: individuals choose one node at random and link to it
with probability p, then they choose a neighbour of that node and link with
probability q. Our model produces power laws with empirical exponents ranging
from 1.5 upwards and clustering co-efficients ranging from 0 up to 0.5
(consistent with many real networks). For small p and q=1, the model produces
super-hub networks, and we prove that for p=0 and q=1, the proportion of
non-hubs tends to 1 as the network grows. We show that power-law degree
distributions, small world clustering and super-hub networks are all outcomes
of this, more general, yet conceptually simple model.
