GitHub Growth Appears Scale Free

Update of Thursday, August 17, 2017: It's looks like we can chalk up another one for the scale-free model (described below) as Github apparently surpasses 20 million users. Outgoing CEO Wanstrath mentioned this number in an emailed statement to Business Insider.

"As GitHub approaches 700 employees, with more than $200M in ARR, accelerating growth, and more than 20 million registered users, I'm confident that this is the moment to find a new CEO to lead us into the next stage of growth. ....."

The Original Analysis

In 2013, a Redmonk blogger claimed that the growth of GitHub (GH) users follows a certain type of diffusion model called Bass diffusion. Here, growth refers to the number of unique user IDs as a function of time, not the number project repositories, which can have a high degree of multiplicity.

In a response, I tweeted a plot that suggested GH growth might be following a power law, aka scale free growth. The tell-tale sign is the asymptotic linearity of the growth data on double-log axes, which the original blog post did not discuss. The periods on the x-axis correspond to years, with the first period representing calendar year 2008 and the fifth period being the year 2012.

Exponential Cache Behavior

Guerrilla grad Gary Little observed certain fixed-point behavior in simulations where disk IO blocks are updated randomly in a fixed size cache. For his python simulation with 10 million entries (corresponding to an allocation of about 400 MB of memory) the following results were obtained:

• Hit ratio (i.e., occupied) = 0.3676748
• Miss ratio (i.e., inserts) = 0.6323252

In other words, only 63.23% of the blocks will ever end up inserted into the cache, irrespective of the actual cache size. Gary found that WolframAlpha suggests the relation: \begin{equation} \dfrac{e-1}{e} \approx 0.6321 \label{eq:walpha} \end{equation} where $e = \exp(1)$. The question remains, however, where does that magic fraction come from?

My Year in Review 2011

Some days I wonder if I ever actually accomplish anything anymore. Maybe it's time to just pack it in and become a greeter at Walmart. I know a bit about how queues work, so that should put me a few notches ahead of the competition. And I would expect the competition to be fierce because it's a pretty cushy job; but not every day, apparently.

Before taking the big leap, I decided it might be a good idea to note down some of the technical projects I've worked on this year (over and above the daily grind):

GDAT 2011 in Review

As usual, the Guerrilla Data Analysis Techniques (GDAT) class was a total blast. Motivated students always guarantee that. It would really help our scheduling, however, if people didn't wait until the last nanosecond to register for the class. But given the crazy economic climate, I'm more than happy to do whatever it takes to make GDAT fly.

Guerrillas in the data mist [Photo: P. Newsom]

Some course highlights that you missed:

Q-Q Plots and Power Laws in Database Performance Data

I'm in the process of putting together some slides on how to apply Quantile-Quantile plots to performance data. Q-Q plots are a handy tool for visually inspecting how well your data matches a known probability distribution (prob dsn). If the match is good, the data should line up more or less diagonally in the Q-Q plot. A common usage is to verify normality, i.e. how well the data matches a Normal or Gaussian dsn. In fact, this usage is so common that R even has a separate function called qqnorm() for doing just that.

Anti Log Plots

A sure sign that somebody doesn't know what they're doing is, when they plot their data on logarithmic axes. Logarithmic plots are almost always the wrong thing to use. The motivation to use log axes often arises from misguided aesthetic considerations, rather than any attempt to enhance technical understanding, e.g., trying to "compress" a lot of data points into the available plot width on a page. The temptation to use log plots is also too easily facilitated by tools like Excel, where re-scaling the plot axes is just a button-click away.

Linux Meets Zipf's Law

It's amazing how power laws seem to be seen in everything these days:

A team of researchers from ETH Zürich (Einstein's alma mater) in Switzerland used four decades of data detailing the evolution of open source software applications created for a Linux operating system to confirm the adherence to Zipf's law. The team studied Debian Linux, as it is continuously being developed by more than 1,000 volunteers from around the world. Beginning with 474 packages in 1996, Debian has expanded to include more than 18,000 packages today. The packages form an intricate network, with some packages having greater connectivity than others, as defined by how many other packages depend on a given package.

It's also amazing what passes for physics these days:

T. Maillart.; D. Sornette; S. Spaeth, and G. von Krogh. “Empircal Tests of Zipf’s Law Mechanism in Open Source Linux Distribution.” Physical Review Letters 101 218701 (2008).