igraph-help
[Top][All Lists]

## Re: [igraph] pagerank implementation questions

 From: stainless steel some one Subject: Re: [igraph] pagerank implementation questions Date: Sun, 4 Mar 2007 20:45:52 -0800 (PST)

```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
> 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

```

reply via email to