远见与创新

Zipf, Power-laws, and Pareto - a ranking tutorial
Lada A. Adamic, HP lab

---

They are all about small occurrences are common, whereas large instance are rare.

• Zipf’s law: y ~ r^(-b), y: size, r: rank
  word frequency: 1932; city sizes: 1949
• Pareto’s law: P[X > x] ~ x^(-k)
  Income distribution, 1896
• power law distribution: P[X = x] ~ x^(-(k+1)) = x^(-a)
  a = 1+k (where k is the Pareto distribution shape parameter).

Long-tailer is another words for them. And they shall be a line appeared on a log-log plot.

Zipf’s law and the Internet
Lada A. Adamic, Bernardo A. Huberman, HP

Internet is Zipf’s law. It differs from classic Erdös-Rényi random graphs model that has a Poisson node degree distribution.

The important attribute of Zipf’s law is: It is Scale-free, i.e. elements that are much larger than the mean still have finite probability. On the other hand, in Gaussian distribution, e.g. human heights, they are extremely unlikely.

Huberman intuitive growth model explain the Zipf’s law in Internet in 1999 with three assumptions:

• Proportional page number growth Det(x) = K*x in each site
• Page number growth rates are different among different sites
• Exponential sites number growth

With these assumptions, Albert developed a new random graph growth model in 2002.

Ripeanu found P2P network E2E connections distribtution shifts from Zipf to two-sided Zipf in 2002. With this oberservation, Adamic shown in 2001, broadcast method need to be evolved to routing query to high degree nodes to obtain congestion relief and quick response.

[Questions]

1. Power-law network is a natural selection, but pure P2P is pursuiting a real even degree distribution. Is P2P fighting with natural rule?
2. How Broadcast method is proved to need to be evolved by Adamic?

[Future Reading]

• Huberman, B. and Adamic, L. (1999). Growth Dynamics of the World Wide Web. Nature 401, 131.
• Huberman, B. A. (2001). The Laws of the Web. The MIT Press.
• Erdös, P. and Rényi, A. (1960). On the Evolution of Random Graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 17-61.
• Albert R. and Barabasi A.-L. (2002). Statistical mechanics of complex networks. Review of Modern Physics 74, 47-94.
• Adamic, L.A., Lukose, R.M., Puniyani, A.R., and Huberman, B.A. (2001). Search in
  Power-Law Networks. Physical Review E 64: 046135.

Technorati : Pareto, Power-laws, Zipf