[Networkit] random walks / hitting probability

Henning Meyerhenke henning.meyerhenke at kit.edu
Thu Oct 5 15:31:14 CEST 2017

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,

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)

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20171005/0eeee78d/attachment.p7s>

More information about the NetworKit mailing list