Empirical Tests of Zipf’s Law Mechanism in Open Source Linux Distribution

Zipf’s power law is a ubiquitous empirical regularity found in many systems, thought to result from proportional growth. Here, we establish empirically the usually assumed ingredients of stochastic growth models that have been previously conjectured to be at the origin of Zipf’s law. We use exceptionally detailed data on the evolution of open source software projects in Linux distributions, which offer a remarkable example of a growing complex self-organizing adaptive system, exhibiting Zipf’s law over four full decades.

Figure 1

(Color Online) Log-log plot of the number of packages in four Debian Linux Distributions with more than $C$ in-directed links. The four Debian Linux Distributions are Woody (19.07.2002) (orange diamonds), Sarge (06.06.2005) (green crosses), Etch (15.08.2007) (blue circles), Lenny (15.12.2007) ($\mathrm{\text{black}}+$’s). The inset shows the maximum likelihood estimate (MLE) of the exponent $\mu$ together with two boundaries defining its 95% confidence interval (approximately given by $1\pm 2/\sqrt{n}$, where $n$ is the number of data points using in the MLE), as a function of the lower threshold. The MLE has been modified from the standard Hill estimator to take into account the discreteness of $C$.

Figure 2

Left panel: Plots of $\Delta C$ versus $C$ from the Etch release (15.08.2007) to the latest Lenny version (05.05.2008) in double logarithmic scale. Only positive values are displayed. The linear regression $\Delta C=R\times C+C_0$ is significant at the 95% confidence level, with a small value $C_0=0.3$ at the origin and $R=0.09$. Right panel: same as left panel for the standard deviation of $\Delta C$.

Figure 3

Dependence of $R(\Delta t)$ and $\Sigma (\Delta t)$ defined, respectively, by $R(\Delta t)\equiv ⟨\Delta C/C⟩$ and (5) as a function of their time interval $\Delta t$ for the 66 time intervals that can be formed between all the Debian releases in our database (which includes the four major Debian releases from 19.07.2002 to 15.12.2007 as well as the several Lenny releases from 18.03.2008 to 05.05.2008 in intervals of 7 days). The error bars show the 95% confidence intervals, obtained by shuffling 1000 times the linear regression residuals. The straight lines represent the best linear fits. The existence of a genuine linear dependence of $R$ as a function of $\Delta t$ cannot be rejected ($p<0.05$) and has a high significance level (square of correlation coefficient ${\mathcal{R}}^2=0.93$). The regression of $\Sigma$ versus $\sqrt{\Delta t}$ enjoys the same high statistical confidence ($p<0.05$ and ${\mathcal{R}}^2=0.97$).

Figure 4

The right panel shows that the exponent $\mu$ of the distribution of $C$’s of new packages appearing between successive unstable Lenny releases separated by one week is a power law with exponent $\mu \simeq 1.5$; the left panel show that the same power law has a smaller exponent closer to 1 as one considers the new packages appearing between two more distant releases. We have verified that this effect is systematic in our database. The exponents $\mu$ are obtained by maximum likelihood, adapted to the discreteness of $C$ values. The thin lines defined the 95% confidence intervals.