Re: [igraph] signal diffusion and weighted networks

[Tamas Nepusz]

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.