Stationary distribution for directed graph

Question

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random walk. I don't know how to compute the stationary distribution of random walk in such sparse directed graph.Is there any suggestion?

Answer 1

If I understand the problem correctly, you need to construct a transition probability matrix $P=(p_{ij})$ where the probability $p_{ij}$ of transitioning from vertex $i$ to vertex $j$ is $1/\mathrm{deg}^{\mathrm{out}}(i)$, where $\mathrm{deg}^{\mathrm{out}}(i)$ denotes the out degree of vertex $i$. One you have $P$, the stationary distribution (if it exists) is the eigenvector corresponding to eigenvalue $1$; the eigenvector is normalised so that it sums to $1$.

Here's a simple worked example. For the graph:

the transition probability matrix is $$P=\left(\begin{array}{ccc} 0 & 1 & 0 \\ \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ 1 & 0 & 0 \\ \end{array}\right).$$ Here the stationary distribution is the eigenvector $$\vec{v}=(\tfrac{2}{5},\tfrac{2}{5},\tfrac{1}{5})$$ since $\vec{v}P=\vec{v}$.