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?
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.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top