Preferential attachment in randomly grown networks

• We model a graph grown by the addition of vertices and edges at rates one and δδ respectively.
• Model parameter determines the degree of preferential attachment for new edges.
• Preferential attachment leads to a power-law degree distribution.
• Increasing preference for high degree vertices accelerates emergence of a giant component.
• Positive assortative mixing reported in the case of no preference is lost in the power-law regime.

We reintroduce the model of Callaway et al. (2001) as a special case of a more general model for random network growth. Vertices are added to the graph at a rate of 11, while edges are introduced at rate δδ. Rather than edges being introduced at random, we allow for a degree of preferential attachment with a linear attachment kernel, parametrised by mm. The original model is recovered in the limit of no preferential attachment, m→∞m→∞. As expected, even weak preferential attachment introduces a power-law tail to the degree distribution. Additionally, this generalisation retains a great deal of the tractability of the original along with a surprising range of behaviour, although key mathematical features are modified for finite mm. In particular, the critical edge density, δcδc which marks the onset of a giant network component is reduced with increasing tendency for preferential attachment. The positive degree–degree correlation introduced by the unbiased growth process is offset by the skewed degree distribution, reducing the network assortativity.