Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a directed graph $G = (V,E)$, to define a random walk on $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution (as mentioned in this paper) I used a one step teleporting random walk (also mentioned in the paper) to obtain the transition probability matrix from the matrix $W$ (matrix of weights of edges). So if there is any edge outs from the current vertex ($u$), and if $d$ is the probability of jumping uniformly to any vertex of the graph, then $u$ jumps to other nodes with the total probability (with $(1-d)$) jumps randomly to any other vertex and with probability $d*(W(u,v)/dp(u))$ jumps to a vertex $v$ adjacent to it): $$(1-d)*1/n+d*(W(u,v)/dp(u))$$ where $dp$ is the outdegree edges from vertex $u$ and $v$ is any node jumps to it from $u$. If there is no edge outs from $u$, the jump is from $u$ to any other node uniformly with probability $1/n$ . So, I obtain the transition matrix easily by this equation. Is it correct or the transition matrix must be obtained in recursive process and I do only one step of it?

share|cite|improve this question
Ooo, :) It seems to be correct and it works and the results were very nice.I maybe answer my question in this week in details because first I must learn Mathjex for equations. – Fatime Apr 13 '13 at 4:37
@Byron thanks for edit. – Fatime Apr 27 '13 at 14:08
It's pretty common; the word "probablity" appears over 60 times on this site. It's almost as bad as "continous", one of my pet peeves. – Byron Schmuland Apr 27 '13 at 14:15
@ByronSchmuland You are right. I must improve my English. – Fatime Apr 27 '13 at 14:30
Bad spelling affects native English speakers too. – Byron Schmuland Apr 27 '13 at 14:36

Your Answer


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

Browse other questions tagged or ask your own question.