22
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ Mike, I think it would be very interesting to see the plot that you are looking at. Would you mind editing your answer to include it? One thing that I immediately noticed is that the implication regarding power laws and preferential attachment is backwards. While (some) preferential attachment schemes generate power-law degree distributions, the reverse implication is not true (i.e., it's not the only way). Some information on what kind of network you are looking at might also be helpful. Cheers. $\endgroup$ – cardinal Apr 22 '12 at 13:16
  • 1
    $\begingroup$ I mean preferential attachment is simply another name for "rich gets richer" effect right? If that's the case then linear (power law) network degree distribution is just one of many degree distributions which can demonstrate preferential attachment? In other words, as long as the gradient of the curve is negative on a log-log plot then there is some elements of preferential attachment, regardless of the distribution? Then the difference between log-normal and power-law degree distribution is not so much on whether there is preferential attachment but the proportionality of it. $\endgroup$ – Mike Apr 22 '12 at 13:53
  • 1
    $\begingroup$ Note that preferential attachment is a (stochastic) process which generates power-law degree distributions for a network. The slope of the line will change according to the scaling exponent for a power-law, but in the case of a lognormal, the plot will not be linear, even in the tail. The gradient of a survival distribution will always be negative no matter what the effect is. (Why?) $\endgroup$ – cardinal Apr 22 '12 at 14:19
  • $\begingroup$ That's a very good edit. Thanks, Michael! The lognormal fit in the region you've shown is pretty remarkable. It looks like it might be breaking down a little bit in the tail. $\endgroup$ – cardinal Apr 22 '12 at 14:21
  • $\begingroup$ Thanks for your reply again cardinal. So do you agree that preferential attachment is still at work in the network I'm observing? Another question which leads on is whether the network is scale-free. If preferential attachment is at work in the network and as long as the network takes new members then the network can be classified as scale-free even though the network degree distribution isn't linear. This is where I'm not very sure. $\endgroup$ – Mike Apr 22 '12 at 15:20
12
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ did you mix up < and > when talkinga bout the p-value for the upper tail fit? $\endgroup$ – David Nathan Nov 24 '17 at 13:41
  • $\begingroup$ The p-value conditions in this comment are right. The p-values referred to here come from section 4.1 of arxiv.org/abs/0706.1062, where large values represent good fits and small values represent bad fits. See in particular footnote 8 on the bottom of page 17. $\endgroup$ – Jonathan S. Mar 13 '18 at 4:18
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.