Propertities of Networks and Random Graphs

1. Key network propertities

1. degree distribution $p(k)$p(k)
probability that a randomly chosen node has degree k:
$p(k)=N_k/N$p(k)=Nk​/N
$in\ which, N_k=number\ of\ nodes\ with\ degree\ k$in which,Nk​=number of nodes with degree k.
2. path length $h$h

• distance: the shortest path between two nodes
• diameter: the maximum distance between any pair of nodes in a graph
• average path length
  $\overline h=\frac 1{2E_{max}}\cdot \sum_{i,j\neq i}h_{ij}$h=2Emax​1​⋅i,j​=i∑​hij​
  $E_{max}=\frac{n(n-1)}{2}$Emax​=2n(n−1)​
  3. clustering coefficient (for undirected graph) $C$C
  to what extent do my friends know each other
  $C_i=\frac {2e_i}{k_i(k_i-1)}$Ci​=ki​(ki​−1)2ei​​
  $in\ which, e_i\ is\ the\ number\ of\ edges\ of\ node_i$in which,ei​ is the number of edges of nodei​; $k_i\ is\ the\ degree\ of\ node_i$ki​ is the degree of nodei​.
  4. connectivity $s$s
  size of the largest connected component
  BFS (breath first search)

2. Erdos_Renyi random graphs

$G_{np}$Gnp​: undirected graph with $n$n nodes where each edge $(u,v)$(u,v) appears i.i.d. (independently) with probability $p$p
$G_{nm}$Gnm​: undirected graph with $n$n nodes and $m$m edges picked uniformly at random

$G_{np}$Gnp​:

1. degree distribution

• it is binomial:
  $P(k)={n-1\choose k}p^k(1-p)^{n-1-k}$P(k)=(kn−1​)pk(1−p)n−1−k
• average degree:
  $\overline k=p(n-1)\approx{pn}$k=p(n−1)≈pn
• variance
  $\sigma^2=p(1-p)(n-1)$σ2=p(1−p)(n−1)
• an important property
  $\frac{\sigma}{\overline k}=\sqrt{ \frac{1-p}{p}\frac{1}{n-1}}\approx{\frac{1}{(n-1)^{1/2}}}$kσ​=p1−p​n−11​​≈(n−1)1/21​
  $as\ n\ increases, the\ distribution\ becomes\ narrow\, and\ the\ degree\ of\ a\ node\ is\ in\ the\ vincinity\ of\ k$as n increases,the distribution becomes narrowand the degree of a node is in the vincinity of k

2. clustering coefficient

• def:
  $given\ C_i=2e_i/k_i(k_i-1)$given Ci​=2ei​/ki​(ki​−1)
  then:
  $the\ expected\ E(e_i)\ is\ p\cdot k_i(k_i-1)/2$the expected E(ei​) is p⋅ki​(ki​−1)/2
  then:
  $E(C_i)=p=\frac{\overline k}{n-1}\approx \frac {\overline k}{n}$E(Ci​)=p=n−1k​≈nk​

3. path length

• fact: the path length of E-R graph is $O(\log n)$O(logn)
• def: expansion: $\alpha$α
  
  basically it means given a subset of nodes $S$S, the proportion of edges leaving S.
  

4. connectivity

• $\overline k>1,largest\ conn.\ comp.\ exists$k>1,largest conn. comp. exists
  
  Although real networks are not random graphs, the model $G_{np}$Gnp​ is still extremely useful. It is the reference model for the rest of the class.

3. small-world network

1. key characteristics: high clustering and low path length
   
2. generating approach:
   
3. property:
   

4. Kronecker graph model