I want to calculate the probability of seeing vertex $v_j$ in a random walk in less than $K$ steps from vertex $v_i$ for every pair of vertices. Is there any approach for this problem in polynomial time? Actually I want to calculate the $p(v_j|v_i)$ in a window of width $K$, but my problem is that there might be more than one path from $v_i$ to $v_j$.

  • $\begingroup$ What do you know about the graph? If the graph is finite or regular or something, this sounds a lot easier than in full generality. $\endgroup$ – quarague Feb 14 at 10:29
  • $\begingroup$ Yeah, we know that graph is finite but not regular, may be with power law degree distribution. $\endgroup$ – user137927 Feb 14 at 10:41
  • $\begingroup$ If the graph is finite, you can solve this with a version of the adjacency matrix. Compute the matrix $A$ that gives you the probability for every vertex after a random walk with $1$ step. To figure out what happens after $K$ steps you only need the $K$th power fo this matrix $A^K$. Note that you only need to compute this matrix once and then can use it for all vertices. $\endgroup$ – quarague Feb 14 at 12:01
  • $\begingroup$ I thought there might be a better solution with less time complexity that matrix multiplication. Thanks a lot for your help. $\endgroup$ – user137927 Feb 14 at 12:16
  • $\begingroup$ Matrix powers can be computed a lot more efficiently than by just multiplying a matrix by itself over and over again by diagonalizing it first. Whether this actually helps depends on the size of your graph and the range of $K$. If the graph is small and $K$ is big or you want a lot of different values of $K$, this is much faster. If the graph is huge and you only need relatively low values of $K$ just multiplying the matrices might be faster. $\endgroup$ – quarague Feb 14 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.