Thank you.
I tried to become familiar with page.rank and I guess it is an excellent
idea but
I still have some problems. For instance, the results are highly variable
> netz
IGRAPH UNW- 328 11582 --
+ attr: name (v/c), x (v/n), y (v/n), weight (e/n)
First try:
page.rank (netz, personalized=c(2), damping=0.85)$vector[1:20]
rs72621144 rs76583332 rs116426014 rs9773882 rs71512836
156288
1.520751e-01 1.341455e-01 1.616638e-04 1.034574e-02 1.865783e-03
2.938891e-04
156375 rs9773471 rs7822515 rs7836416 rs7843227
rs11776856
3.365556e-04 1.061015e-02 3.606822e-04 1.026718e-02 1.062957e-02
1.666288e-03
rs10086982 rs10103818 rs7387067 rs78768549 rs117362856
rs28878202
3.298816e-04 7.856723e-05 1.059628e-02 1.051060e-02 1.066612e-05
5.524765e-05
rs13249796 rs3008288
1.250746e-02 1.411444e-03
Second try
page.rank (netz, personalized=2, damping=0.85)$vector[1:20]
rs72621144 rs76583332 rs116426014 rs9773882 rs71512836 156288
NaN NaN NaN NaN NaN NaN
156375 rs9773471 rs7822515 rs7836416 rs7843227 rs11776856
NaN NaN NaN NaN NaN NaN
rs10086982 rs10103818 rs7387067 rs78768549 rs117362856 rs28878202
NaN NaN NaN NaN NaN NaN
rs13249796 rs3008288
NaN NaN
Actually, I am wondering for the NaNs. I get highly variable resu Why are
there NaNs for my vertex of interest (personalized=2).
A cutting of my adjacency matrix:
6 x 6 sparse Matrix of class "dgCMatrix"
rs72621144 rs76583332 rs116426014 rs9773882 rs71512836 156288
rs72621144 . 0.363491 . . . .
rs76583332 0.363491 . . 0.622703 0.219751 .
rs116426014 . . . . 0.259331 0.417368
rs9773882 . 0.622703 . . 0.219216 .
rs71512836 . 0.219751 0.259331 0.219216 . 0.366768
156288 . . 0.417368 . 0.366768 .
The results become less variable if I change the damping factor, for
instance damping=0.5.
page.rank (netz, personalized=2, damping=0.5)$vector[1:10]
rs72621144 rs76583332 rs116426014 rs9773882 rs71512836
156288
5.022980e-01 2.525437e-01 5.145497e-05 5.698979e-03 1.567815e-03
7.693787e-05
156375 rs9773471 rs7822515 rs7836416
9.686269e-05 5.320426e-03 1.012695e-04 5.149335e-03
A damping factor closer to 0 (in comparison to the default of 0.85) makes
it more likely to stay in the neighborhood of the personalised vertex. Is
this correct? So a lower damping factor gives a better characterisation of
the closely surrounding network. May I say that?
Do I get NaNs for damping=0.85 because the random walk ends far away of my
vertex of interest?
If you are interested to check my igraph object, you are invited to
download it via:
https://drive.google.com/file/d/0BxUQUYo5KHcLQ0UwNzd4R1BxdzA/view?usp=sharing
Thanks
Hermann
2015-03-17 22:25 GMT+01:00 Tamas Nepusz <[email protected]>:
> Sounds like personalized PageRank to me, although PageRank is based on
> random
> walks and not diffusion. Basically, when you calculate the personalized
> PageRank vector using a single node as a seed, it will tell you for every
> node
> the probability of ending up at that particular node after an infinitely
> long
> random walk that occasionally teleports back to the seed node (with a
> certain
> probability at every step).
>
> Since your graph is undirected, an infinitely long random walk that never
> jumps
> back to the seed node would converge to a state where each node is visited
> with
> a probability proportional to its degree, so that's probably not too
> useful for
> you. That's why it makes sense for the random walk to jump back to the seed
> node occasionally. This is controlled by the "damping" parameter of the
> PageRank algorithm -- it specifies the probability of *not* jumping back
> to the
> seed node at each step of the random walk.
>
> Here's an example in Python:
>
> # generate a graph
> g = Graph.GRG(100, 0.2)
>
> # calculate the personalized PageRank of vertex 0 with a sensible damping
> pr = g.personalized_pagerank(damping=0.85, reset_vertices=[0])
>
> Then you can take the personalized PageRank vector and select the vertices
> with
> the highest PageRank values.
>
> If you are really interested in physically realistic diffusion equations,
> try
> googling for "heat diffusion on graphs" -- it has been studied extensively
> before. Basically, you can construct a set of differential equations that
> tell
> you how the "temperature" of each vertex would change as "heat" diffuses
> over
> the network. One can then make a connection between the eigenvectors of
> certain
> matrices derived from the (normalized, weighted) adjacency matrix of the
> graph
> and infer how fast the heat would diffuse over the network by looking at
> the
> eigenvectors. But this is not implemented in igraph.
>
> Tamas
>
> On 03/17, Hermann Norpois wrote:
> > Yes. I was not precise. I am not sure if diffusion is the correct term
> ...
> > Imagine the edges are tubes and the weights are diameters and then you
> > inject blue ink in vertex i the blue color will distribute according to
> the
> > weighted edges (please forget the diluation effect). I wish to know what
> > are the first 30 vertices that are affected. Thanks
> >
> > 2015-03-17 12:48 GMT+01:00 Tamas Nepusz <[email protected]>:
> >
> > > Hello,
> > >
> > > > I have a non-directed weighted network and I want to know: What are
> the
> > > > neighboruing vertices of a certain vertex. Of course, I can use
> > > > graph.neighborhood but it does not take into account that the edges
> are
> > > > weighted. I am looking for a method that reflects how a signal
> "diffuses"
> > > > if it starts at a certain vertex. Could anybody give me a hint?
> > > Please provide a more detailed definition of what you mean by
> "diffusion"
> > > --
> > > the neighborhoods of vertices do not change if the edges are weighted
> so
> > > I'm
> > > pretty sure that you mean something else here and not just the
> neighboring
> > > vertices.
> > >
> > > --
> > > T.
> > >
> > > _______________________________________________
> > > igraph-help mailing list
> > > [email protected]
> > > https://lists.nongnu.org/mailman/listinfo/igraph-help
> > >
>
> > _______________________________________________
> > igraph-help mailing list
> > [email protected]
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> --
> T.
>
> _______________________________________________
> igraph-help mailing list
> [email protected]
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
