Database Reference
In-Depth Information
The general form of a power law relating x and y is log y = b + a log x . If we raise the
base of the logarithm (which doesn't actually matter), say e , to the values on both sides of
this equation, we get y = e b e a log x = e b x a . Since e b is just “some constant,” let us replace it
by constant c . Thus, a power law can be written as y = cx a for some constants a and c .
EXAMPLE 1.8 In Fig. 1.3 we see that when x = 1, y = 10 6 , and when x = 1000, y = 1. Making
the first substitution, we see 10 6 = c . The second substitution gives us 1 = c (1000) a . Since
we now know c = 10 6 , the second equation gives us 1 = 10 6 (1000) a , from which we see a
= −2. That is, the law expressed by Fig. 1.3 is y = 10 6 x 2 , or y = 10 6 / x 2 .
We shall meet in this topic many ways that power laws govern phenomena. Here are
some examples:
(1) Node Degrees in the Web Graph : Order all pages by the number of in-links to that
page. Let x be the position of a page in this ordering, and let y be the number of in-links
to the x th page. Then y as a function of x looks very much like Fig. 1.3 . The exponent
a is slightly larger than the −2 shown there; it has been found closer to 2.1.
(2) Sales of Products : Order products, say topics at Amazon.com , by their sales over the
past year. Let y be the number of sales of the x th most popular topic. Again, the func-
tion y ( x ) will look something like Fig. 1.3 . we shall discuss the consequences of this
distribution of sales in Section 9.1.2 , where we take up the matter of the “long tail.”
(3) Sizes of Web Sites : Count the number of pages at Web sites, and order sites by the
number of their pages. Let y be the number of pages at the x th site. Again, the function
y ( x ) follows a power law.
(4) Zipf's Law : This power law originally referred to the frequency of words in a collec-
tion of documents. If you order words by frequency, and let y be the number of times
the x th word in the order appears, then you get a power law, although with a much
shallower slope than that of Fig. 1.3 . Zipf's observation was that y = cx 1/2 . Interest-
ingly, a number of other kinds of data follow this particular power law. For example,
if we order states in the US by population and let y be the population of the x th most
populous state, then x and y obey Zipf's law approximately.
The Matthew Effect
Often, the existence of power laws with values of the exponent higher than 1 are explained by the Matthew effect .
In the biblical Topic of Matthew , there is a verse about “the rich get richer.” Many phenomena exhibit this behavior,
where getting a high value of some property causes that very property to increase. For example, if a Web page has
many links in, then people are more likely to find the page and may choose to link to it from one of their pages as
Search WWH ::




Custom Search