Re: [igraph] pagerank implementation questions

[Tamas Nepusz]

Hi,

> 1) Should the range of the damping factor be [0, 1],
> i.e. damping could take == 0, or == 1.0, the boundary
> value?
Yes, it can be 0 or 1 as well, but it does not make much sense...  
However, you are right that this constraint really has no practical  
gain, so feel free to remove it and we'll remove it from upcoming  
releases as well.

> But by the formula on
> http://en.wikipedia.org/wiki/PageRank
>
> is the answer wrong?
Well, the above mentioned page has a couple of PageRank formula  
variants. I used the first one in the section "PageRank algorithm  
including damping factor", which is exactly the one that was written  
by Brin & Page's original paper. (However, in the very same paper,  
they state that the sum of PageRanks is always one, which is clearly  
not the case when we use their formula). A solution might be to add a  
boolean switch to the list of igraph_pagerank arguments which decides  
whether to use the normalization or not. This will break the existing  
igraph_pagerank API, however, so it looks like it will only be  
included in the next major release (igraph 0.4). If you really need  
this functionality, it's easy to add, you only have to modify lines  
1720 and 1755 to use (1-damping)/no_of_nodes instead of just (1- 
damping).

> 2) in the examples/simple/igraph_pagerank.c, is there
> any way I can specify weight of each edge? (not just
> connectivity, but also the *weight* of each edge?)
Not yet, but patches are welcome :) (This will also break the API,  
since you have to specify the weight vector as an input argument, so  
it will be included in igraph 0.4 at the earliest)

> 3) how the pagerank calculation is actually
> implemented?
>
> -- is it by performing (niter) number of iterations?
> -- or by solving the eigenvector of the adjacency
> matrix?
igraph_pagerank makes at most niter iterations, but stops earlier if  
the PageRank vector changes less than eps during an iteration.

> I suspect it's done by iterations; if this is true, is
> there any plan to actual solve the eigenvector of the
> adjacency matrix in the future?
Not yet (mostly because of lack of time), but patches are welcome :)

--
Tamas Nepusz <address@hidden>             MTA RMKI, BME MIT