Interpreting the difference between lognormal and power law distribution (network degree distribution)

Question

First off, I'm not a statistician. However, I have been doing statistical network analysis for my PhD.

As part of the network analysis, I plotted a Complementary Cumulative Distribution Function (CCDF) of network degrees. What I found was that, unlike conventional network distributions (e.g. WWW), the distribution is best fitted by a lognormal distribution. I did try to fit it against a power law and using Clauset et al's Matlab scripts, I found that the tail of the curve follows a power law with a cut-off.

Dotted line represents power law fit. Purple line represents log-normal fit. Green line represents exponential fit.

What I'm struggling to understand is what this all mean? I've read this paper by Newman which slightly touches on this topic: http://arxiv.org/abs/cond-mat/0412004

Below is my wild guess:

If the degree distribution follows a power law distribution, I understand that it means there is linear preferential attachment in the distribution of links and network degree (rich gets richer effect or Yules process).

Am I right in saying that with the lognormal distribution I'm witnessing, there is sublinear preferential attachment at the beginning of the curve and becomes more linear towards the tail where it can be fitted by a power law?

Also, since a log-normal distribution occurs when the logarithm of the random variable (say X) is normally distributed, does this mean that in a log-normal distribution, there are more small values of X and less large values of X than a random variable that follows a power law distribution would have?

More importantly, with regards to network degree distribution, does a log-normal preferential attachment still suggest a scale-free network? My instinct tells me that since the tail of the curve can be fitted by a power law, the network can still be concluded as exhibiting scale-free characteristics.

Answer 1

I think it will be helpful to separate the question into two parts:

1. What is the functional form of your empirical distribution? and
2. What does that functional form imply about the generating process in your network?

The first question is a statistics question. If you've applied the methods of Clauset et al. for fitting the power-law distribution and those methods gave you a $p>0.1$ for the upper-tail fit, then you're allowed to say that the upper tail (looking at your figure, this is $x\geq15$ or so) is plausibly power-law distributed. If the methods gave you $p<0.1$ then you can't say that, even if the fit looks good to the eye. Deciding whether the log-normal fit is better means basically doing the same thing. Can you reject that model as a generating process for the degree distribution data you have? If not, then you're allowed to put the log-normal into the "plausible" category.

As a small technical point, degrees are integer quantities, while a log-normal distribution requires a continuous variable, so the two are not really compatible (unless you are only talking about $x\gg1$ when the difference between integers and real values for these kinds of questions becomes negligible). To do the statistics properly, you'd want to write down the pdf for a "log-normally" distributed integer quantity, derive estimators for it and apply those to your data.

The second question is actually harder of the two. As some people pointed out in the comments above, there are many mechanisms that produce power-law distributions and preferential attachment (in all its variations and glory) is just one of many. Thus, observing a power-law distribution in your data (even a genuine one that passes the necessary statistical tests) is not sufficient evidence to conclude that the generating process was preferential attachment. Or, more generally, if you have a mechanism A that produces some pattern X in data (e.g., a log-normal degree distribution in your network). Observing pattern X in your data is not evidence that your data were produced by mechanism A. The data are consistent with A, but that doesn't mean A is the right mechanism.

To really show that A is the answer, you have to test its mechanistic assumptions directly and show that they also hold for your system, and preferably also show that other predictions of the mechanism also hold in the data. A really great example of the assumption-testing part was done by Sid Redner (see Figure 4 of this paper), in which he showed that for citation networks, the linear preferential attachment assumption actually holds in the data.

Finally, the term "scale-free network" is overloaded in the literature, so I would strongly suggest avoiding it. People use it to refer to networks with power-law degree distributions and to networks grown by (linear) preferential attachment. But as we just explained, these two things are not the same, so using a single term to refer to both is just confusing. In your case, a log-normal distribution is completely inconsistent with the classic linear preferential attachment mechanism, so if you decide that log-normal is the answer to question 1 (in my answer), then it would imply that your network is not 'scale free' in that sense. The fact that the upper tail is 'okay' as a power-law distribution would be meaningless in that case, since there is always some portion of the upper tail of any empirical distribution that will pass that test (and it will pass because the test loses power when there isn't much data to go on, which is exactly what happens in the extreme upper tail).

Answer 2

Such a cool question. I'm having a related conversation about this associated with a question I asked elsewhere on CrossValidated. There, I asked whether the gamma distribution was a good distribution to use in a simulation of a social network where the probability of ties is endogenous to some continuous "popularity" characteristic of nodes. @NickCox suggested that I use the lognormal distribution instead. I replied that the lognormal distribution has some theoretical justification as the underlying process describing popularity because popularity could be interpreted as the product of many positive-valued random variables (e.g., wealth, income, height, sexual prowess, fighting prowess, IQ). This makes more sense to me than the theoretical justification for the power law, and it jives with the empirical data, which suggests that the power law's shape is too inflexible to explain the cross-network variation in the degree distribution. The lognormal, by comparison, has a very flexible shape, with the mode approaching zero for high variance. Furthermore, it makes sense that the skewness of the degree distribution should increase with the variance due to the preferential attachment effect.

In sum, I think that the lognormal distribution fits your data best because the lognormal distribution describes the underlying process of degree distribution formation better than the power law or exponential distributions.

Answer 3

Coming to this site after counting my bubble distributions and using power law for viscosity data.

Skimming through the example data sets in the power law paper by Clauset et al. they have put up some real horrors of data sets, far from the power law data sets to support their argument. Just from common sense I certainly wouldn't have tried to fit a power law function to the whole data range for most of them. However, self-scaling behaviour in the real world may be valid across a part of an observed system, but break down when some system property reaches a physical or functional limit.

The very readable papers below refer to growth-curve fitting for ecologists, with a good discussion on power law and related distributions, based on observation-based models of population behaviour.

The author is much more pragmatic than Clauset et al. Quoting: "...if the aim is only a best fit and scales outside the scale window of the data set are not discussed, any model may suffice given that it produces a good fit and produces no maxima or minima inside the scale window studied." "One is often forced to fit the same model, as other researchers have applied to their data, in order to be able to compare parameter values, but one can do this in addition to the application of a better fitting model or models with better expected shapes, or both." Restful words.

Tjørve, E. (2003). Shapes and functions of species-area curves: A review of possible models. Journal of Biogeography, 30(6), 827-835.

Tjørve, E. (2009). Shapes and functions of species-area curves (ii): A review of new models and parameterizations. Journal of Biogeography, 36(8), 1435-1445.

Answer 4

The above results show that degree distribution can be both power law and lognormal, which may suggest that small world and scale free properties co-exist in the network under studied. To examine whether the network is scale free (with constant scaling parameter) with preferential attachment, experimental design is often required. In the article of Sid Redner mentioned above, growth rate is used to understand the growth mechanism. While Gallos, Song and Makse use boxes to cover the network, and conclude that network degree distribution follows power law distribution, if NB(lB) ~ lB^-dB. Or examing the relationships between cluster coefficient and degree (whether the relationship satisfies power law). Otherwise, it is discussed that hierachical networks have both small world and scale free network properties. (typing Fractal scale free, there are many articles suggested by google).