A package repository's dependency graph grows by adding one new package at a time
PHYSICS · Subjective · Fermi University Physics · Mathematical Methods for Physics · Thermal, Statistical & Complex Systems · Complex and collective systems
Many Parts, One Behaviour, Ch Growing networks: preferential attachment and scale-free degree distributions
Problem
A package repository's dependency graph grows by adding one new package at a time. Each new package depends on m=1 existing package, chosen with probability proportional to its degree, the number of dependency links it already takes part in, made or received (a Barabási-Albert rule, attachment probability Πk=k/(2mt)). (a) Write the rate equation for Nk(t), the expected number of packages of degree k, and state what assumption makes it a mean-field equation. (b) Using the exact stationary solution pk=2m(m+1)/[k(k+1)(k+2)], compute p1, p2 and p3, and check that these three terms alone already account for more than 85% of all packages.