Re: [igraph] signal diffusion and weighted networks

[Hermann Norpois]

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 <address@hidden>:

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 <address@hidden>:
>
> > 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
> > address@hidden
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
> >

> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help


--
T.

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help