Random walk methods measure distance using random walk instead of deterministic paths. A representative methods is Personalized PageRank algorithm, and is defined as:

$\mathbf{S}_{RW} [u,v]=\mathbf{q}_u[v]+\mathbf{q}_v[u]$

where $\mathbf{q}_u[v]$ is the stationary probability that a random walk starts at $u$ and visits $v$. Intuitively, the similarity between a pair of nodes is the sum of probabilities of reaching each node from the other node through random walk.

University of Notre Dame

Global overlap measures are statistics that can measure relationships between two nodes in the same community graph even if these two nodes are not directly connected, while local overlap measures only consider the local relationship between nodes that are in the local node neighborhood. There are several types of global overlap measures:

1)	Katz index

2)	Leicht, Holme, and Newman (LHN) similarity

3)	Random walk methods  


Global Overlap Measures

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Katz index is the most basic type of global overlap measure, and it equals to weighted sum of number of path of all lengths:

$\mathbf{S}_{Katz} [u,v]=\sum_{i=1}^{\infty}\beta^i \mathbf{A}^i [u,v]$

where $\beta$ is a user-defined parameter, and $\mathbf{A}$ is the adjacency matrix. The larger $\beta$ is, the more important longer paths are. It can be proved that:

 $\mathbf{S}_{Katz}=(\mathbf{I}-\beta \mathbf{A})^{-1}-\mathbf{I}$


Katz Index

LHN similarity is defined as:

$\mathbf{S}_{LNH} [u,v]=\mathbf{I}[u,v]+\frac{2m}{d_ud_v}\sum_{i=1}^{\infty}\beta^i \lambda_1^{1-i} \mathbf{A}^i [u,v]$

where $d_u$ and $d_v$ are degree of nodes $u$ and $v$, and $\lambda_1$ is the largest eigenvalue, and $m$ is total number of edges in the graph. And it can be proved that:

 $\mathbf{S}_{LNH}=2\alpha m\lambda_1\mathbf{D}^{-1}(\mathbf{I}-\frac{\beta}{\lambda_1} \mathbf{A})^{-1}\mathbf{D}$

The idea of LHN is that, becasue Katz similarity gives much more higher scores for high degree nodes, it wants to solve this issue by normalizing actual number of observed path using expected number of path, whcich is $\frac{\mathbf{A}^i}{\mathbb{E}[\mathbf{A}^i]}$. And $\mathbb{E}[\mathbf{A}^i]$ can be estimated through $d_u, d_v$ and $\lambda_1$. 

Learn Before

Related