[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] pagerank implementation questions
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] pagerank implementation questions |
Date: |
Mon, 5 Mar 2007 13:48:52 +0100 |
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
- [igraph] pagerank implementation questions, stainless steel some one, 2007/03/04
- Re: [igraph] pagerank implementation questions, stainless steel some one, 2007/03/04
- Re: [igraph] pagerank implementation questions, stainless steel some one, 2007/03/04
- Re: [igraph] pagerank implementation questions, Tamas Nepusz, 2007/03/05
- Re: [igraph] pagerank implementation questions, stainless steel some one, 2007/03/05
- Re: [igraph] pagerank implementation questions, Tamas Nepusz, 2007/03/06
- Re: [igraph] pagerank implementation questions, Gabor Csardi, 2007/03/06
- Re: [igraph] pagerank implementation questions, stainless steel some one, 2007/03/06
- igraph license, was: Re: [igraph] pagerank implementation questions, Gabor Csardi, 2007/03/06
Re: [igraph] pagerank implementation questions,
Tamas Nepusz <=
Re: [igraph] pagerank implementation questions, Tamas Nepusz, 2007/03/05