[Networkit] random walks / hitting probability

Matthieu Latapy Matthieu.Latapy at lip6.fr
Fri Oct 6 14:10:09 CEST 2017


Dear Henning,

Thank you for your answer. I think I will try the algebraic approach and compare it to a direct spreading from neighbor to neighbor, since l is small in my case.

All the best,
ML

On Thu, Oct 05, 2017 at 03:31:14PM +0200, Henning Meyerhenke wrote:
> Dear Matthieu,
> 
> You are right, there is nothing readily implemented, but the machinery
> is in place (in principle). I see two options:
> 
> - You use the algebraic interface, define your random walk matrix P and
> compute P times distribution vector (in total l times).
> 
> - You code the matrix vector product in graph lingo -- similar to
> PageRank, eigenvector centrality and related algorithms
> 
> Hope this helps,
> Henning
> 
> 
> 
> Am 05.10.17 um 15:23 schrieb Matthieu Latapy:
> > Dear all,
> > 
> > Let me first thank you for this great graph library :)
> > 
> > I need to compute, for a given vertex v and a given path length l, the probability to hit any other vertex in my graph with a random walk of length at most l and starting from v.
> > 
> > I could not find a ready-to-use function for this, although it seems to me that everything needed already is implemented. In particular, there may be a way to use Pagerank for this, but I am unsure.
> > 
> > Does anyone have hints?
> > 
> > Best regards,
> > ML
> > 
> 
> -- 
> 
> =======================================
> Prof. Dr. Henning Meyerhenke
> 
> Affiliation since Sep 15, 2017:
> University of Cologne
> 
> Previous affiliation:
> Karlsruhe Institute of Technology (KIT)
> =======================================
> 



-- 

---------------
Matthieu Latapy
http://www.complexnetworks.fr
-----------------------------



More information about the NetworKit mailing list