Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2024 / Paper 1 / D6 / b / iii / Solution

For the Barabási-Albert model, choose a connected seed graph on $m_0$ vertices, the number $m\le m_0$ of new edges per added vertex, and a final size $n$. A complete seed with $m_0\ge 2$ suffices. Add one vertex at a time, attaching it to $m$ distinct existing vertices selected with weights proportional to their current vertex degrees. Exclude duplicate edges and self-loops.

Increasing $n$ creates a larger network and permits older hubs to grow. Increasing $m$ makes the graph denser, with asymptotic average vertex degree $2m$, and tends to shorten graph distances. The seed affects early structure and the oldest hubs; standard linear preferential attachment gives a robust large-size tail exponent.

Its asymptotic degree distribution is $P(k)\propto k^{-3}$, so it is a scale-free network. Hubs produce short average shortest path length, but elevated clustering coefficients are not automatic: $m=1$ with a tree seed gives a triangle-free tree, and clustering decreases with size in the standard model. The strict clustered small-world network property is therefore not guaranteed.^[ref]