The Katz index is a global overlap measure equal to the weighted sum of the number of paths of all lengths between two nodes: $$\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}$$

University of Notre Dame

Google

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

Random walk methods measure distance using random walks instead of deterministic paths. A representative method is the Personalized PageRank algorithm, 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 a random walk.

Random Walk Methods

Katz Index

Leicht, Holme, and Newman (LHN) similarity is defined as: $$\mathbf{S}_{LHN} [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 the degrees of nodes $$u$$ and $$v$$, $$\lambda_1$$ is the largest eigenvalue, and $$m$$ is the total number of edges in the graph. It can be proved that: $$\mathbf{S}_{LHN}=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 because Katz similarity gives much higher scores for high degree nodes, LHN similarity solves this issue by normalizing the actual number of observed paths using the expected number of paths, which is $$\frac{\mathbf{A}^i}{\mathbb{E}[\mathbf{A}^i]}$$. The expected value $$\mathbb{E}[\mathbf{A}^i]$$ can be estimated through $$d_u$$, $$d_v$$, and $$\lambda_1$$.

Learn Before

Related