Albert-Barabasi model

Question

According to Remco Hofstad's book on Random graphs, for the Albert Barabasi model, the degree of the i^{th} node diverges almost surely (Exercise 8.8 of the first volume).

But isn't this counter-intuitive since the asymptotic distribution is a power law ?

I mean to ask how come the proportion of vertices having degree 1, for example, can be so high, asymptotically, when each node's degree diverges almost surely ?

Answer 1

There is no contradiction between the two observations. More precisely, the two observations are:

For any fixed vertex $v_i$, as time goes to infinity, the degree of $v_i$ diverges

and

At any fixed time, a large fraction of vertices have degree $1$. (More generally, the degree distribution at any fixed time follows a power law.)

(Note that in order to get vertices of degree $1$, we should be looking at the $m=1$ case of the model, giving us a tree; in general, the degree distribution still follows a power law, but all degrees are at least $m$.)

Preferential attachment models are also called "the rich get richer" models. Extending that analogy, you can think of degree distributions in the Barabási–Albert model as a "pyramid scheme".

• At any time $t$, a large fraction of the vertices in the system are "newcomers", and still have the degree we started with. It's possible that some vertices have been around for a long time, and still unluckily have low degree, but most vertices that have been around for a long time are "rich, and getting richer".
• If we skip ahead to time $100t$ (for example), then the vertices we saw at time $t$ are just $1\%$ of the vertices in the system now. It is still true that a large fraction of the vertices in the system have low degree, but for the most part, that refers to the vertices that have appeared recently. The $1\%$ of vertices that had already appeared by time $t$ generally have pretty high degree, because they've had at least $99t$ time steps in which their degree could increase. (It's possible that some have gotten unlucky, but most haven't.)

In general, as time increases, the very old vertices tend to be "rich" (and have high degree), but most vertices are not very old. This explains the power law distribution of degrees. However, for any fixed vertex $v_i$, if we wait long enough, eventually $v_i$ will become a very old vertex. (At time $100i$, it is in the top $1\%$ of vertices by age, so we expect it to have pretty high degree.)

The reason that this works out for the vertices, while pyramid schemes generally don't work out for humans, is that the number of vertices grows without limit, whereas pyramid schemes aren't able to attract infinitely many people.