INF 674 S4: Power Laws

Céline Comte & Fabien Mathieu

2016 - 2017

If you want to deepen your theoretical knowledge of power laws, you can read (this is not mandatory):

• Chapter 7 from the book Epidemics and Rumours in Complex Networks.
• MEJ Newman, Power laws, Pareto distributions and Zipf's law. Contemporary Physics Vol. 46 , Iss. 5, 2005.

Further readings:

• M. Mitzenmacher, A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics 1.2, 226-251, 2004.
• A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, Graph structure in the Web. Comput. Netw. 33, 1-6, 309-320, 2000.

Outline

• Definition
• Power Laws in the wilde
• Generative models
  • Barabási-Albert random graphs
  • Yule process

Definition

Heavy-tailed distribution

A continuous real random variable $X$ has a power-law distribution if its tail fails according to some power: $$ \mathbb{P}\left\{ X > x \right\} = \left( \frac{x_{min}}{x} \right)^\beta, \quad \forall x \ge x_{min}. $$

• $\beta > 0$ is the shape paremeter
• $x_{min} > 0$ is the scale parameter

Distribution functions

• Probability distribution function $$ f(t) = \frac{\beta {x_{min}}^\beta}{t^{\beta + 1}}, \quad \forall t \ge x_{min}. $$
• Cumulative distribution function $$ \mathbb{P}\left\{ X \le x \right\} = 1 - \left( \frac{x_{min}}{x} \right)^\beta, \quad \forall x \ge x_{min}. $$

How to recognize them?

• Probability distribution function $$ f(t) = \frac{\beta {x_{min}}^\beta}{t^{\beta + 1}}, \quad \forall t \ge x_{min}, $$ can be rewritten as $$ \ln(f(t)) = \ln(\beta {x_{min}}^\beta) - (\beta + 1) \ln(t), \quad \forall t \ge x_{min}. $$

• The graph of the probability distribution function of a random variable with a power law is a line on a log-log plot.

Power Laws in the wilde

Zipf's Law for rankings

• Discrete version of the power law
• A discrete random variable $X$ which takes its values in $\{1,\ldots,N\}$ has a Zipf's distribution with parameter $\tau > 0$ if $$

  \mathbb{P}\{ X = k \}
  = \frac{ \frac1{k^\tau} }{ \sum_{n=1}^N \frac1{n^\tau} },
  \quad \forall k = 1,\ldots,N.
  

  $$

Web graph

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, Graph structure in the Web. Comput. Netw. 33, 1-6, 309-320, 2000.

Web graph

Concretely:

"... there are many small elements contained within the Web, but few large ones. A few sites consist of millions of pages, but millions of sites only contain a handful of pages. Few sites contain millions of links, but many sites have one or two. Millions of users flock to a few select sites, giving little attention to millions of others."

L.A. Adamic and A.H. Bernardo, Zipf’s law and the Internet. Glottometrics 3.1, 143-150 2002.

Other examples

• Word frequency

  "Zipf's law states that given some corpus of natural language utterances, the frequency of any word is inversely proportional to its rank in the frequency table. Thus the most frequent word will occur approximately twice as often as the second most frequent word, three times as often as the third most frequent word, etc.: the rank-frequency distribution is an inverse relation." See Wikipedia, Zipf's law.

Other examples

• Number of telephone calls per user and per day
• Content popularity

Generative models

Barabási-Albert random graphs

A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science, 286, 509–512, 1999.

(Undirected) Random graph model

• At time $t = 0$, we consider a deterministic initial (undirected) graph $G(0)$
• At each step $t \ge 1$, a new node is added to the graph and is attached to one existing node:
  • With probability $0 \le \alpha < 1$, all existing nodes can be chosen with the same probability,

(Undirected) Random graph model

• With probability $1 - \alpha$, the probability of choosing a node is proportional to its degree.

(Undirected) Random graph model

• The graph obtained at the end of step $t$ is denoted by $G(t)$.

• We consider the random variables
  $X_i(t) =$ Number of nodes with degree $i$ at time $t$, for all $i \ge 1$, $t \ge 1$.

"Law of large numbers"

• For all $i \ge 1$, we have $$ \frac{X_i(t)}t \to c_i \text{ almost surely when } t \to +\infty, $$ where the sequence $(c_i)_{i \ge 1}$ satisfies $$ c_i \sim \frac{C}{i^{\beta + 1}} \text{ as } i \to +\infty, $$ for some constant $C > 0$, where $$ \beta = \frac{3-\alpha}{1-\alpha} - 1 = 2 + \frac{2 \alpha}{1 - \alpha} \ge 2. $$

Intuition of the proof

• Let $c_1 = \frac2{3 + \alpha}$ and $$

  \frac{c_i}{c_{i-1}} = \frac{\alpha + \frac{1-\alpha}2 (i-1)}{1 + \alpha + \frac{1-\alpha}2 i},
  \quad \forall i > 1.
  

  $$
• For all $i > 1$, \begin{align*}

  \frac{c_i}{c_{i-1}}
  = 1 - \frac{3 - \alpha}{2 + 2 \alpha + (1 - \alpha)i}
  = 1 - \frac1i \frac{3 - \alpha}{1 - \alpha} + O\left( \frac1{i^2} \right).
  

  \end{align*}

Intuition of the proof

• Consequently, \begin{align*}

  c_i
  &= c_1 \prod_{j=2}^i \left( 1 - \frac\beta{j} + O\left( \frac1{j^2} \right) \right).
  

  \end{align*}

Intuition of the proof

• Then, we have intuitively \begin{align*}

  &\ln\left( \prod_{j=1}^i \left( 1 - \frac\beta{j} \right) \right) \\
  &= \sum_{j=1}^i \ln\left( 1 - \frac\beta{j} \right)
  \approx \sum_{j=1}^i - \frac\beta{j}, \\
  &= - \beta \sum_{j=1}^i \frac1j
  \approx - \beta \ln(i).
  

  \end{align*}

Yule process

G. U. Yule, A mathematical theory of evolution based on the conclusions of Dr. J. C. Willis, Philosophical Transactions of the Royal Society of London B, 213, 21–87, 1925.

Historical context

• Introduced by Yule in 1925 to study the evolution of the number of species in a genus.
• (Wikipedia) "A genus (/ˈdʒiːnəs/, pl. genera) is a taxonomic rank used in the biological classification of living and fossil organisms in biology. In the hierarchy of biological classification, genus comes above species and below family."

Definition

• At time $t = 0$, we consider a deterministic initial state of the species.
• At each step $t \ge 1$, an existing species chosen uniformly at random creates a new one by mutation:
  • With probability $\alpha$, the new species is so different from the pre-existing ones that it defines a new genus,
  • With probability $1 - \alpha$, it belongs to the same genus as the species that created it.

Equivalent (undirected) random graph model

• At time $t = 0$, we consider a deterministic initial (undirected) graph $G(0)$
• At each step $t \ge 1$, a new node is added to the graph and is attached to the older nodes as follows:
  • With probability $0 \le \alpha < 1$, it is not attached to any node (thus creating a new connected component),
  • With probability $1 - \alpha$, it is attached to an existing node chosen uniformly at random.

Equivalent (undirected) random graph model

• The graph obtained at the end of step $t$ is denoted by $G(t)$.
• One connected component = one genus.

• We consider the random variables
  $X_i(t) =$ Number of connected components with $i$ nodes at time $t$, for all $i \ge 1$, $t \ge 1$.

Asymptotic power law

• For all $i \ge 1$, we have $$ \frac{X_i(t)}t \to c_i \text{ almost surely when } t \to +\infty, $$ where the sequence $(c_i)_{i \ge 1}$ satisfies $$ c_i \sim \frac{C}{i^{\beta + 1}} \text{ as } i \to +\infty, $$ for some constant $C > 0$, where $$ \beta = \frac{3-\alpha}{1-\alpha} - 1 = 2 + \frac{2 \alpha}{1 - \alpha} \ge 2. $$