Clustering

• What fraction of my friends are friends of each other?

• $Cl_i(g)$ = #{kj in g | k, j in $N_i(g)$} / #{kj | k, j in $N_i(g)$}

• Average clustering: $$Cl^{avg}(g) = \sum_i Cl_i(g)/n $$

• Overall clusterig:

  • $Cl(g)$ = $\sum_i$ #{kj in g | k, j in $N_i(g)$} / $\sum_i$ #{kj | k, j in $N_i(g)$}

Clustering in a Poisson Random Network

• Average and Overall clustering tend to 0, if max degree is bounded and network becomes larege:

  • $Cl(g)$ = $\sum_i$ #{kj in g | k, j in $N_i(g)$} / $\sum_i$ #{kj | k, j in $N_i(g)$} is simply p

• If degree is bounded, then p(n-1) is bounded

• So p goes to 0 as n grows

High? Clustering coefficients

• Prison friendships

  • 0.31 (MacRae 60) vs 0.0134 (G(n, p) model)

• CO-authorships

  • 0.15 math (Grossman 02) vs 0.00002
  • 0.09 biology (Newman 01) vs 0.00001
  • 0.19 econ(Goyal et al 06) vs 0.00002

• www

  • 0.11 for web links (Adamic 99) vs 0.0002