Re: [igraph] Mean Time-First Passage

[Sylvain Loiseau]

Hello,

Thanks for your answer.

Unfortunately I'm not an expert at all. I try to do my best but be aware  
that I may be completly wrong about the state of the art in this field.

> Btw. you mean some numerical approximation, or it is possible to
> calculate this exactly for general networks? (I guess not, but I am
> not really up to date with random walks.)

> Can you suggest some algorithms for this?

I have been told about the paper : "Algorithms for estimating relative  
importance in networks", that the authors kindly have made available:

http://www.datalab.uci.edu/papers/white_smyth.pdf

It contains an interesting comparaison of shortest path (p. 269) vs "Mean  
Time-First passage" indicator of importance or proximity between two nodes.

If I understand correctly, it seems that it is possible to calculate  
exactly an expected value, without approximation: "A useful property of  
using mean first passage times, besides having a natural Markov  
interpretation, is that one can directly compute a mean first passage  
matrix giving the mean first passage times for all pairs of nodes." (270).

Yours,
Sylvain


> Best,
> Gabor
>
> On Wed, May 20, 2009 at 8:00 PM, Sylvain Loiseau <address@hidden>  
> wrote:
> > Hello all,
> >
> > Is there any implementation of an algorithm for computing Mean  
> > Time-First
> > passage in random walk with the igraph library?
> >
> > Thanks for it anyhow,
> > Best,
> > Sylvain
> >
> > --
> > Sylvain Loiseau
> > address@hidden
> >
> >
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > http://lists.nongnu.org/mailman/listinfo/igraph-help

--
Sylvain Loiseau
address@hidden