Graph Global Overlap Measure: Random Walk Similarity

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]$¹,

$$ \mathbf q_u = c \mathbf P \mathbf q_u + (1-c) \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, i.e., … .

The solution is¹,

$$ \mathbf q_u = (1-c) ( \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$.