**Personalized PageRank (PPR)** replaces the uniform teleport vector in PageRank with a **preference vector** $$\mathbf{v}$$ concentrated on a chosen seed set, so the stationary mass measures proximity to those seeds rather than global importance:

$$\mathbf{r} = d\, P^{\top} \mathbf{r} + (1-d)\, \mathbf{v}.$$

Jeh and Widom (2003) showed that PPR is linear in $$\mathbf{v}$$ and can be decomposed and scaled efficiently; Haveliwala (2002) used topic-biased $$\mathbf{v}$$ vectors for topic-sensitive search. **Local PageRank** (Andersen, Chung, and Lang, 2006) computes an $$\varepsilon$$-approximate personalized PageRank vector with an **approximate push** algorithm whose runtime depends on the support of the output rather than on the total graph size, making PPR practical on large graphs. All three variants share a defining property: scores are **stationary distributions of damped random walks**, so a node's value reflects the **summed mass across all reaching paths**, with longer paths damped multiplicatively by $$d$$.

Personalized / Local PageRank Propagation

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.

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

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

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

Learn After