Re: [igraph] signal diffusion and weighted networks

[Tamas Nepusz]

> I still have some problems. For instance, the results are highly variable
Which igraph version are you using? Earlier versions of igraph used ARPACK for
PageRank calculations and these versions had some convergence problems,
especially in the case of disconnected graphs.

Another problem could be your usage of the personalized=... argument. The
documentation of the R interface says this:

        Optional vector giving a probability distribution to
        calculate personalized PageRank. For personalized PageRank,
        the probability of jumping to a node when abandoning the
        random walk is not uniform, but it is given by this vector.
        The vector should contains an entry for each vertex and it
        will be rescaled to sum up to one.

So, you need to provide a vector of length 328 there if your graph has 328
vertices, and all of its elements should be zero except the single vertex that
your random walk should jump back to. (I wonder why the R interface gives no
error in this case when the personalization vector is too short).

> 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?
Yes, that's true, although damping values close to zero mean that the random
walk has only a very small chance (or no chance at all) to escape from the seed
vertex at all. For example, if your damping value is 0.25, it means that for
3 out of 4 trials, the random walker will jump back to the seed, so the
probability of being one step away from the seed is only 0.25; the probability
of being two steps away is 0.25 * 0.25 (not counting the possibility that
a two-step random walk may go back to the seed nevertheless if the neighbor of
the seed where you jumped to has a low degree).

> Do I get NaNs for damping=0.85 because the random walk ends far away of my
> vertex of interest?
Nope, that is probably a bug -- either because you are using an old version of
igraph, or because the personalize=... argument is wrong.

> If you are interested to check my igraph object, you are invited to
> download it via:
I have checked it and it seems to be the case that the problem is in the usage
of the personalize=... argument. If you use a vector of length vcount(netz),
then it works:

> pers <- rep(0, vcount(netz))
> pers[2] <- 1
> page.rank(netz, personalize=pers)
> order(pr$vector, decreasing=T)[1:20]
[1]  2 68 53 55 64 49 61 63 47 62 42 43 48 29 32 44 45 25 26 56

You can even plot the graph and color the vertices according to their
personalizd PageRank score to get an idea of how the random walk "diffuses" on
your network.

-- 
T.