Lecture 2

Degree Distribution: $P_l=\frac{\text{\# of v whose degree = }l}{n}$

• Key to understanding the outcome of a spreading process in the graph

Lecture 3

Vertex connectivity $\kappa_v$: minimum number of vertices to remove to make the graph disconnected

Edge connectivity $\kappa_e$: minimum number of edges to remove to make the graph disconnected

$\kappa_v\le\kappa_e\le k_{\min}$

There are $\kappa_v/\kappa_e$ vertex-independent/edge-independent paths between every pair of nodes

Local Clustering Coefficient:

$C_i=\frac{\Delta_i=\text{\# of pairs of neighbors that are adjacent}}{C_{k_i}^2}$

Average Clustering Coefficient: $<C>=\frac1n\sum_{i=1}^nC_i$

Global Clustering Coefficient: $C_\Delta=\frac{3\times\text{\# of triangles in the graph}}{\sum_{i=1}^nC_{k_i}^2}$

ACC focus on local structure around each node, while GCC focus on global structure. In GCC, high-degree nodes have more influence.

Lecture 4

Betweenness Centrality: $x_i=$ pairs of nodes that i is on their shortest path.

Two Distinct Cases of Degree Distributions:

• Poisson Degree Distribution

  $P_l=\frac{e^{-<k>}(<k>)^l}{l!},l=0,1,\dots$

• Power-Law Degree Distribution (Scale-free networks)

  $P_l=c\cdot l^{-\gamma},\gamma>1,l=1,2,\dots$

  If $2<\gamma<3$, mean degree is finite but degree variance is infinite.

  There are hubs with much larger degree.

  Robust to Random Attacks and fragile to Targeted Attacks.