Graph Global Overlap Measure: Random Walk Similarity
#Graph #Basics #Clustering
Random Walk
Construct a stochastic transfer matrix $P$ by normalizing the adjacency matrix $\mathbf A$ using the node degrees of the target nodes,
$$ \mathbf P = \mathbf A \mathbf D^{1}, $$
where $\mathbf A$ is the adjacency matrix Graph Adjacency Matrix A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$ for the graph Public Domain, Link and $\mathbf D$ is a diagonalized matrix with the diagonal elements being the degrees.
Given a random walk associated with $\mathbf P$ that starts from node $u$, we find the probability that visits each node $v$, $\mathbf q_u[v]$^{1},
$$ \mathbf q_u = c \mathbf P \mathbf q_u + (1c) \mathbf e_u, $$
where $\mathbf e_u$ is the onehot encoding of node $u$ and $c$ is a probability that the walk restarts at $u$.
 If $c=0$, we have a constant solution.
 If $c=1$, we have $\mathbf q_u = \mathbf P \mathbf q_u$, which is the Eigenvector Centrality of a Graph Eigenvector Centrality of a Graph Given a graph with adjacency matrix $\mathbf A$, the eigenvector centrality is $$ \mathbf e_u = \frac{1}{\lambda} \sum_{v\in\mathcal V} \mathbf A[u,v] \mathbf e_v, \qquad \forall u \in \mathcal V. $$ Why is it called Eigenvector Centrality The definition is equivalent to $$ \lambda \mathbf e = \mathbf A\mathbf e. $$ Power Iteration The solution to $\mathbf e$ is the eigenvector that corresponds to the largest eigenvalue $\lambda_1$. Power iteration method can help us get this eigenvector, … .
The solution is^{1},
$$ \mathbf q_u = (1c) ( \mathbf I  c \mathbf P )^{1} \mathbf e_u. $$
Random Walk Similarity
The random walk similarity is defined using $\mathbf q_u$,
$$ \mathbf S_{\text{RW}}[u, v] = \mathbf q_u[v] + \mathbf q_v[u], $$
which is symmetry under permutation of $u$ and $v$.
L Ma (2021). 'Graph Global Overlap Measure: Random Walk Similarity', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graphglobaloverlaprandomwalksimilarity/.
Table of Contents
Current Ref:

cards/graph/graphglobaloverlaprandomwalksimilarity.md