Welcome to MathOverflow

Question

1

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?

flag	asked Feb 22 at 14:42 Fatime 11●3

meij · Accepted Answer · 2013-02-22 15:30:05Z UTC

2

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.

answered Feb 22 at 15:30

meij
227●3

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 at 5:04

Stationary distribution for directed graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

Your Answer

Not the answer you're looking for? Browse other questions tagged markov-chains random-walk graph-theory cluster-algebras or ask your own question.

Welcome to MathOverflow

How to write math

Stationary distribution for directed graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.