有向图中的随机游走方法

目前基于随机游走的 graph embedding 方法都是针对无向图进行随机游走，但是在有向图中如何进行随机游走？本文介绍下有向图中的随机游走资料。

有向图随机游走

基于 PageRank 的思路进行有向图的随机游走。

定义1 (有向图) 有向图（directed graph）记作 $G=(V, E)$ ，其中 $V$ 和 $E$ 分别表示结点和有向边的集合。

比如，互联网就可以看作是一个有向图，每个网页是有向图的一个结点，网页之间的每一条超链接是有向图的一条边。

从一个结点出发到达另一个结点，所经过的边的一个序列称为一条路径（path）, 路径上边的个数称为路径的长度。

如果一个有向图从其中任何一个结点出发可以到达其他任何一个结点，就称这个有向图是强连通图（strongly connected graph）。

假设 $k$ 是一个大于 1 的自然数，如果从有向图的一个结点出发返回到这个结点的路径的长度都是 $k$ 的倍数，那么称这个结点为周期性结点。

如果一个有向图不含有周期性结点，则称这个有向图为非周期性图（aperiodic graph)，否则为周期性图。

**定义2（随机游走模型）**给定一个含有 $n$ 个结点的有向图，在有向图上定义随机游走（ random walk）模型，即一阶马尔可夫链，其中结点表示状态，有向边表示状态之间的转移;

假设从一个结点到通过有向边相连的所有结点的转移概率相等。具体地，转移矩阵是一个 $n$ 阶矩阵 $M$

$M=\left[m_{i j}\right]_{n \times n}$

第 $i$ 行第 $j$ 列的元素 $m_{ij}=1/k$ ，表示节点 $j$ 有 $k$ 个出边，矩阵每列元素代表出边概率；矩阵 $M$ 中每个元素非负且每列元素和为1，即 $M$ 是随机矩阵。

举例上图中的有向图对应的概率转移矩阵为

$M=\left[\begin{array}{cccc} 0 & 1 / 2 & 1 & 0 \\ 1 / 3 & 0 & 0 & 1 / 2 \\ 1 / 3 & 0 & 0 & 1 / 2 \\ 1 / 3 & 1 / 2 & 0 & 0 \end{array}\right]$

有向图的概率转移矩阵是非对称的，可能会导致其它的问题？