## 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 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 + (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 .

The solution is1,

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

Planted: by ;

L Ma (2021). 'Graph Global Overlap Measure: Random Walk Similarity', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graph-global-overlap-random-walk-similarity/.