NETWORK THEORY and APPLICATIONS

Basic Definitions

  • $A$: adjacency matrix
  • $n$: number of nodes in the network
  • $deg(i)$: degree of node $i$
  • $l(i,j)$: distance (geodesic or shortest path) between nodes $i$ and $j$
  • $P(i,j)$: number of shortest path between nodes $i$ and $j$
  • $P_{k}(i,j)$: number of shortest path between nodes $i$ and $j$ that path through node $k$

Centrality Measures

Centrality definitions in Wikipedia

Degree centrality

Measure how connected is a node

(1)
\begin{equation} C_{i}^{Deg}={deg(i)}/{n-1} \end{equation}

Closeness centrality

Measure how far node $i$ is away from other nodes

(2)
\begin{align} C_{i}^{C}=(n-1)/\sum_{j}{l(i,j)} \end{align}

Decay Centrality

Measure how information decay between node $i$ and the rest of the network.

(3)
\begin{align} C_{i}^{D}=\sum_{j \ne i} \delta_{l(i,j)} \end{align}

where $0<\delta<1$

Betweenness Centrality

(4)
\begin{align} C_{k}^{B}=\frac{\sum_{i,j \ne k} P_{k}(i,j)/P(i,j)}{\binom{n-1}{2}} \end{align}

Eigenvector Centrality

Centrality is proportional to the sum of neighbors' centralities

(5)
\begin{align} A C^{E}=\lambda C^{E} \end{align}

Wikipedia: In general, there will be many different eigenvalues $\lambda$ for which an eigenvector solution exists. However, the additional requirement that all the entries in the eigenvector be positive implies (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.

Bonacich Centrality

There is base value for each node $i$: $b=a * deg(i)$, where $a$ is constant

(6)
\begin{align} C^{Bonacich}=a (A+b A^2 +b^2 A^3+\dots)=a \sum_{i=1}{b^{i-1}A^i} \end{align}

Diffusion Centrality

(7)
\begin{align} C^{Diff}(p,T)=\sum_{t=1}^{T}{(p A)^t}= \begin {cases} T=1: \propto C^{Deg} \\ p<1/\lambda&\text{and}& T \gg 1: \propto C^{Bonacich} \\ p>1/\lambda&\text{and}& T \gg 1: \propto C^E \end{cases} \end{align}

Threshold and Phase Transition

Growing Networks

Random grow

(8)
\begin{align} \begin{cases} \frac{d(deg(i,t))}{dt}=m(i/t)\\ where: deg(i,t=i)=m \text{ (i.e. when i_th node born)} \end{cases} \Longrightarrow deg(i,t)=m(1+\ln(t/i)) \\ \text{fraction of nodes with degree}< deg_{E} \text{, i.e., } i>t e^{-\frac{deg_{E}-m}{m}} \Rightarrow F_t=\frac{t-t e^{-\frac{deg_{E}-m}{m}}}{t} \end{align}

Preferential Attachment

The nodes with higher degree have higher chance to be connected to a new born nodes

(9)
\begin{align} \text{Expected degree for node $i$ born at $m<i<t$} \begin{cases} \frac{d(deg(i,t))}{dt}=m \frac{deg(i,t)}{2tm}\\ where: deg(i,t=i)=m \text{ (i.e. when i_th node born)} \end{cases} \Longrightarrow deg(i,t)=m(t/i)^{1/2} \\ \text{fraction of nodes with degree}< deg_{E} \text{, i.e., } i>\frac{t m^2}{deg_E^{2}} \Rightarrow F_t=\frac{t-i}{t}=\frac{t-\frac{t m^2}{deg_E^{2}}}{t} \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License