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$. 

Leicht, Holme, and Newman (LHN) Similarity

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.

Random Walk Methods  

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  


University of Notre Dame

Neighborhood overlap metrics between pairs of nodes are useful in helping us quantify the extent to which a pair of nodes are related, which is import in tasks such as predicting the existence of an edge between two nodes.

Neighborhood Overlap Detection

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

Local overlap statistics are simply functions of the number of common neighbors two nodes share. Given a neighborhood overlap statistic $S[u,v]$, a common strategy is to assume that the likelihood of an edge (u,v) is simply proportional to $S[u,v]$

-> $P(A[u,v] = 1) \propto S[u,v]$

A few examples of local overlap statistics include:

- simple neighborhood overlap measure
- Sorenson index
- Salton index
- Jaccard overlap
- Resource Allocation (RA) and Adamic-Adar (AA) indexes

Learn Before

Related

Learn After