# Stationary distribution for directed graph

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?

-

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$.
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}$.
If Matlab's results are different (I don't use this package myself), then it's probably either giving you $(1,1,\tfrac{1}{2})$, or something similar, which, when normalised gives $(\tfrac{2}{5},\tfrac{2}{5},\tfrac{1}{5})$, or that it gives $(1, 1, 1)$, which is the eigenvector of $P^T$ rather than $P$. – Douglas S. Stones Feb 24 '13 at 14:33