An online encyclopedia's article-link network grows one article at a time
PHYSICS · Subjective · Fermi University Physics · Mathematical Methods for Physics · Thermal, Statistical & Complex Systems · Ordinary differential equations
Many Parts, One Behaviour, Ch Growing networks: preferential attachment and scale-free degree distributions
Problem
An online encyclopedia's article-link network grows one article at a time, time t counted in articles. Each new article carries m=6 links, placed on existing articles chosen with probability proportional to their current degree, counting links made and received alike (Barabási-Albert preferential attachment). Treat the degree ki(t) of an article born at time ti as a smooth, continuum-in-time function of t (the mean-field continuum approximation). (a) Using Πi=ki/(2mt) and the fact that a node gains links at expected rate mΠi, write and solve the differential equation for ki(t) with initial condition ki(ti)=m, to obtain ki(t)=m(t/ti)1/2. (b) The encyclopedia now has N=8×105 articles. Estimate the degree of (i) the very first article (ti=1) and (ii) an article created at ti=4×104, both evaluated at t=N. (c) Treating each article's birth time as uniformly distributed over 1≤ti≤N and inverting ki(N)=m(N/ti)1/2, show that the fraction of articles with degree at least k is m2/k2, hence that the continuum degree density is p(k)=2m2k−3 for large k. Compare its coefficient 2m2 with the exact Barabási-Albert coefficient 2m(m+1) for m=6, and give the percentage by which the exact result exceeds the continuum estimate.