Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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:

Example directed 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}$.

share|improve this answer
    
Thanks a lot for your answer and clear example :). I use the eig(p) instruction of Matlab to compute the eigen vector of your example but the result is not the same as your result,Is there a specific point?Thanks again. –  Fatime Feb 24 '13 at 10:52
    
Does this property(I mean the stationary distribution is proportional to left eigenvector corresponding to eigenvalue 1 ) true for every type of graph such as directed or undirected,strongly connected or sparse, periodic or aperiodic, or just for strongly connected aperiodic graph which has unique stationary distribution? –  Fatime Feb 24 '13 at 11:07
    
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
    
Undirected graphs are equivalent to directed graphs with edges pointing in both directions (so it'll work for undirected the same as directed). It will work in all strongly connected aperiodic cases (e.g. these lecture notes (.pdf) make this argument). –  Douglas S. Stones Feb 24 '13 at 14:40
    
Thanks:) for answer and lecture.I also saw this lecture but as mentioned in this lecture "I present a concise proof of the existence and uniqueness of the limit distribution of an ergodic Markov chain."and in lecture Randomness and Computation A Markov chain M is ergodic if and only if:1.The graph GM is irreducible: For every large enough n, there is a positive probability path of length n between any two states.2.The graph GM aperiodic: The GCD of the lengths of positive probability cycles of GM is 1. –  Fatime Feb 24 '13 at 16:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.