The Power Law Paradox, or Why the Power Law Exponent Does Not Mean What You Think It Means

Large networks are often described as having a power-law degree distribution. In other words, the number of nodes having n neighbors is proportional to n−γ, for some number γ (this is the Greek letter Gamma).  Now, it is well-known that this is often not the case, and that many other degree distributions are easily mistaken for a power-law.  Nevertheless, some networks do have power laws, and in these networks, we might think about the meaning of the parameter γ.

Degree distribution of the CiteULike user–tag network

This is the degree distribution of the CiteULike user–tag network.  Using Aaron Clauset’s code, we can find out that it fits a power-law distribution with γ = 1.63.  The code from Aaron Clauset also returns a value of dmin = 1, which means that the power law is valid beginning with minimal degree 1 (i.e., for all nodes).

γ is the slope of the distribution, i.e., when γ is high, the number of nodes with high degree is smaller than the number of nodes with low degree.  We may thus think that a low value of γ denotes a more equal distribution, and that higher and higher values of γ denote more and more unfair degree distributions.  However, this is not the case.  In fact,  the opposite is true: A high value of γ represents a network in which the distribution of edges is fairer.

To measure the equality of the degree distribution, we can use a measure from Economics that has been used to measure the equality of a country’s income distribution. This measure is called the Gini coefficient.  The Gini coefficient can be computed by drawing the so-called Lorenz curve (shown below), and measuring the area that it traces out:

Lorenz curve (blue curve) of the Facebook friendship network

The Lorenz curve, as shown above as a blue curve, consists of all points (X,Y) such that the statement “X percent of the people on Facebook with the smallest number of friends account for Y percent of all friendship links.” For instance, the big black point which lies on the Lorenz curve allows us to state that “The 75% of Facebook users with the least number of friends account for only 25% of all friendship links.” Or, in other words, “The 25% of Facebook users with most friends account for 75% of all friendship links.” If the distribution of friendships among users is maximally equal, then all users have the same number of friends, and the Lorenz curve follows the diagonal of the plot (from the bottom left to the top right).  When the distribution is less equal, the Lorenz curve is nearer to the bottom and right of the plot.  Therefore, the area between the Lorenz curve and the diagonal is an indication of the equality of the degree distribution.  This area is maximally 0.5 (half the square), and therefore we define the Gini coefficient as twice this area, so the Gini coefficient is a measure of equality that goes from 0 (total equality) to 1 (total inequality).

Now we can finally ask:  If two networks with power law degree distributions have two different power law exponents γ, which of the two networks has a higher Gini coefficient?  To find out, we generate networks with perfect power laws, and compute their Gini coefficients. In fact, we don’t have to compute whole networks, it is enough to generate the degree distributions. The result looks like this:

Lorenz curves of perfect power law distributions, with γ ranging from 2.1 to 3.5

The result:  Power law distribution distributions with high γ have a Lorenz curve nearer to the diagonal.  Therefore, a higher value of γ means the distribution is more equal.

This result is somewhat surprising:  We would have thought that a higher slope on the degree distribution plots means that there are even less nodes with many neighbors. However, the opposite is the case.

Notes

(1) The mathematically correct name of a power law distribution is “Zeta distribution”, because the normalizing factor 1^(−γ) + 2^(−γ) + 3^(−γ) + … is exactly the Riemann zeta function of γ.

(2) In this test, γ must be strictly larger than 2, otherwise the distribution mean cannot be defined, simply because 1^−1 + 2^−1 + 3^−1 + … is not defined (see Harmonic series)

References

[1] Fairness on the Web: Alternatives to the Power Law. Jérôme Kunegis & Julia Preusse. WebSci 2012.

Advertisements

5 thoughts on “The Power Law Paradox, or Why the Power Law Exponent Does Not Mean What You Think It Means

  1. Pingback: Lorenz cruve | Hinteler

  2. Hi John

    The code is not available yet. We will make the codes available once we release the analysis code for KONECT. If you want I can send you the Matlab source files via email; just contact me via private message or at kunegis@uni-koblenz.de and give me your email.

    Best
    Jérôme

  3. You are getting this odd result because the Gini coefficient is defined as “as half of the relative mean absolute difference” and power low with exponent lower than 2 does not have mean. You are comparing apples with oranges.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s