Degree Distribution, G(n, p)

  • probability that node has d links is binomial $$\frac{(n-1)!}{d!(n-d-1)!} p^d (1-p)^{n-d-1}$$

  • Large n, small p, this is approximately a Poisson distribution $$\frac{(n-1)^d}{d!} p^d e^{-(n-1)p}$$

  • why Poisson? If you want to approximate this if you want to approximate this formula(binomial formula) for large n and relatively small p.

    • $(1-p)^{n-d-1} \rightarrow e^{-(n-1)p}$
    • $\frac{(n-1)!}{d!(n-d-1)!} \rightarrow \frac{(n-1)^d}{d!}$
    • $\frac{(n-1)!}{(n-d-1)!} \rightarrow (n-1)^d$


  • many isolated nodes
  • several components
  • no component has more than a small fraction of the nodes, just starting to see one large one emerge

Distribution of links per node: Fat tails (Price 1969)

  • More high and low degree nodes than predicted at random
    • Citation Networks - too many with 0 citations, too many with high numbers of of citations to have citations drawn at random
    • "Fat tails" compared to random network

Scale Free Distributions

  • $P(d) = cd^{-a}$

  • $log(P(d)) = log(c) - alog(d)$