Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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 2 down vote accepted

In this algorithm after computing the transition matrix, we should compute the stationary distribution

The stationary distribution is proportional to one of the left or right eigenvectors of the transition matrix, and the corresponding eigenvalue is 1. You can compute this using matlab or other software.

share|improve this answer
    
Thanks a lot for your answer :) .Does this property(I mean the stationary distribution is proportional to left o right eigenvector corresponding to eigenvalue 1 ) true for every type of graph such as directed or undirected,strongly connected or sparse, periodic or aperiodic? –  Fatime Feb 24 '13 at 5:04

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.