Econometa

OK, I finally cleared up what was bothering me about those long tail graphs, prompted by Phil’s comment and helped a lot by this article.

The issue is that long tail graphs have an x axis comprised of items ranked by their y axis value; e.g. for a social bookmarking site we can graph users ranked by how many taggings they’ve performed, and approximate it by an inverse power law:

One nice thing about a ranked graph is that the “area” under the curve is equal to the total value associated with the items spanned on the ranked axis; e.g. for the above graph, the area to the left of the median line represents 50% of the total number of taggings.

However, it seems as if both axes here are carrying essentially the same information (as Phil said, “that bar’s the tallest *and* it’s the first!”). But it turns out that the ranking and the value are in fact separate pieces of information, and a power law shape to the data carries over to more familiar distributions. As I go through how that works, I’ll add some notes on terminology, since it can get a bit confusing.

Firstly, a ranked graph like the one above that follows an exact 1/u inverse power law (i.e. a = 1) is often said to adhere to “Zipf’s Law.” This law originally described how the frequency of use of the nth-most-frequently-used word in any natural language is approximately inversely proportional to n. Subsequently the term Zipf has been used to refer to ranked data that can be fit to several different kinds of curves, but one thing’s for sure: a ranked graph is by definition always decreasing, and is not a probability distribution! (although as we’ll see below, it’s closely related to one).

The key to transforming a ranked graph into a more familiar distribution is this fact: saying that the nth ranked item has a value of y is equivalent to saying that n items have a value of y or more. So for the above graph, saying that the u-th user performed t taggings is equivalent to saying that u users performed t or more taggings:

Now if we invert this graph and turn the number of users performing t or more taggings into the percentage of such users, we arrive at a probability distribution, namely the probability that a randomly selected user performed t or more taggings:

This kind of distribution is called a Cumulative Distribution Function (CDF), and if it follows an inverse power law it is also sometimes referred to as a “Pareto distribution.” A Pareto distribution originally described the percentage of people owning more than x amount of wealth, and led to what is sometimes called the “Pareto principle” or the “80-20 rule”, e.g. that 20% of the population owns 80% of the wealth (note that 80 + 20 = 100 is a coincidence here, another common confusion!).

Finally, we can note that the number of users performing t or more taggings minus the number performing t+1 or more taggings is the number of users performing exactly t taggings, i.e. N(t) - N(t+1) = n(t) = -N’(t); here n(t) is the number of users performing t taggings, and is equal to the negative derivative of the number of users N(t) performing t or more taggings:

This is a familiar Probability Density Function (PDF), and is the more common setting to describing a distribution as fitting a “power law.” Note that if the original ranked graph follows an inverse power law of any kind, so does the corresponding CDF and PDF. The converse is not true, i.e. if a PDF follows an inverse power law, the other graphs only do so if the shape parameter b = 1 + 1/a is greater than 1. Otherwise, the integral of t^-b with b < = 1 does not give a power law.

Of course, after all this, the fact is that at least for me, the original ranked graph is the one that most directly and intuitively answers the question at hand: are most taggings by the most active users? I'd be interested in comments and thoughts, or other graphs that aren't covered above.

** Addendum: Some technical notes, mostly to refresh my own memory

- For a discrete set of outcomes, the function corresponding to non-zero probability values for each outcome is called a Probability Mass Function (PMF).
- A PMF is also sometimes called a Probability Function (PF).
- A histogram (AKA bar chart, step function) can be obtained from a PMF by binning the outcomes into ranges (usually equal or exponential) in a continuous sample space (set of outcomes).
- For a continuous sample space, a Probability Density Function (PDF) gives the probability of an outcome in a specified range by integrating the function over this range. A PMF or its histogram can be approximated by a PDF.
- For a PDF, the probability of any specific outcome is 0, non-zero probabilities only exist by integrating the PDF over an interval of outcomes.
- The "area" under a PMF or PDF must be 1; the area is the sum of all values for a PMF and the integral over the entire sample space for a PDF.
- A power law can only approximate a PDF and must be cut off at its extremeties, since its integral is divergent and so cannot integrate to 1.
- A Cumulative Distribution Function (CDF) F(x) is usually defined in terms of a PDF f(x) by F(b) - F(a) = integral from a to b of f(x), i.e. f(x) = F'(x). This means F(x) is the probability of any outcome less than or equal to x.
- A CDF is also sometimes called a Distribution Function (DF).
- Sometimes a CDF is defined with a different inequality; e.g. a Pareto distribution is a CDF F(x) which is the probability of any outcome *greater* than or equal to x, so that f(x) = -F'(x).
- A Pareto distribution is characterized by a shape parameter a and a minimum value parameter m, and takes the form F(x) = a m^a / x^(a+1) for x >= m, 0 otherwise.

This entry was posted on Monday, June 13th, 2005 at 6:30 pm and is filed under Tagging. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.