Re: [igraph] pagerank implementation questions

[stainless steel some one]

One more question on the converge speed, I tried:

/examples/simple/igraph_pagerank.c

  niter = 100;
  igraph_pagerank(&g, &res, igraph_vss_all(),
directed, niter, 0.001, 0.99);
  print_vector(&res, stdout);

it outputs: 1.01 0.51 1.02 0.01

  niter = 1000;
  igraph_pagerank(&g, &res, igraph_vss_all(),
directed, niter, 0.001, 0.99);
  print_vector(&res, stdout);

output: 1.49 0.75 1.50 0.01

But check their paper:

http://dbpubs.stanford.edu:8090/pub/1999-66

It's quoted that in section 4:

"As can be seen from the graph in Figure 4 PageRank on
a large 322 million link database converges
to a reasonable tolerance in roughly 52 iterations.
The convergence on half the data takes roughly
45 iterations. This graph suggests that PageRank will
scale very well even for extremely large
collections as the scaling factor is roughly linear in
log n."


So why 4 nodes in this small example need 1000
iteration to converge?

Because we didn't set the initial rank value?  and is
there an API in igraph to set the initial value?

Thanks.


--- stainless steel some one <address@hidden>
wrote:

> I didn't dig deep into the source code, but I have
> some questions:
> 
> 1) Should the range of the damping factor be [0, 1],
> i.e. damping could take == 0, or == 1.0, the
> boundary
> value?
> 
> and src/structural_properties.c: line 1682 be
> changed
> to:
> 
>   if (damping< 0 || damping> 1)
> IGRAPH_ERROR("Invalid
> damping factor", IGRAPH_EINVAL);
> 
> 
> I made changed, and did some test: the first example
> output of: examples/simple/igraph_pagerank.c
> 
> passing damping = 1.0, output: 0.00 0.00 0.00 0.00
> passing damping = 0.0, output: 1.00 1.00 1.00 1.00
> 
> But by the formula on 
> http://en.wikipedia.org/wiki/PageRank
> 
> is the answer wrong?
> 
> damping = 0.0, output all should be 1/N = 0.25?
> damping = 1.0, output should be sum(pr(x)/l(x))?
> 
> 
> 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?)
> 
> 
> 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?
> 
> 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?
> 
> Thanks!
> 
> 
> 
> -- Judging people by the non/sense he makes, not the
> name he bears.
> -- intelligence = openminded + compassionate
> 
> "I don't see why the sex of the candidate is
> relevant -- this is after all an academic
> institution not a bath house!" -- Hilbert on
> Noether's not being offered a professorship from
> University of Göttingen.
> 
> 
>  
>
____________________________________________________________________________________
> Looking for earth-friendly autos? 
> Browse Top Cars by "Green Rating" at Yahoo! Autos'
> Green Center.
> http://autos.yahoo.com/green_center/
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
> 


=======================================================================
-- Judging people by the non/sense he makes, not the name he bears.
-- intelligence = openminded + compassionate

"I don't see why the sex of the candidate is relevant -- this is after all an 
academic institution not a bath house!" -- Hilbert on Noether's not being 
offered a professorship from University of Göttingen.
=======================================================================


 
____________________________________________________________________________________
Be a PS3 game guru.
Get your game face on with the latest PS3 news and previews at Yahoo! Games.
http://videogames.yahoo.com/platform?platform=120121