pagerank_numpy, pagerank fails but pagerank_scipy works

[Denzil Correa]

Hello,

I am running PageRank on a weighted DiGraph where nodes = 61634, edges = 28,378. 

pagerank(G) throws me ZeroDivsionError

pagerank_numpy(G) throws me ValueError : array to big 

pagerank_scipy(G) gives me the page ranks though

I can understand that pagerank_numpy error would be due to memory limitations but why does pagerank fail? I tried adding an infinitesimal values to edges with zero weights but the same issues persist. Some pointers would be nice.

I can share my networkx GraphML file if needed.

--

Regards,

Denzil

http://correa.in

[Aric Hagberg]

Hi - I took at look at your graph and I think I see what the problem is.
Your graph has some weights that are not positive. That is causing a
divide by zero error in the nx.pagerank() algorithm. I could see a
case for making the algorithm work correctly for zero weights but not
for negative weights.

The nx.pagerank_scipy() algorithm manages to finish and produce an
answer but I'm not sure what the results mean. I'm surprised it
didn't break.

The nx.pagerank_numpy() algorithm is just running out of memory as you
say. It finds all of the eigenvalues so this is not a practical
choice for bigger problems.

Aric

> --
> You received this message because you are subscribed to the Google Groups
> "networkx-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to networkx-discu...@googlegroups.com.
> To post to this group, send email to networkx...@googlegroups.com.
> Visit this group at http://groups.google.com/group/networkx-discuss.
> For more options, visit https://groups.google.com/groups/opt_out.

[Denzil Correa]

Hi Aric,

Thank you for the reply. You are correct, indeed there were negative weights on my graph. In this case, I would assume that 'pagerank_scipy' should not return a result. In addition, do you think a negative edge weight warning would be good?

[Aric Hagberg]

I'm not sure why the pagerank_scipy() algorithm runs but it could be
that the matrix gets constructed differently in a way that somehow
works for negative weights (didn't look).

In general I am against checking input values and instead try to make
sure if the code fails the error message is helpful.
Aric

[Aric Hagberg]

I made some changes to the PageRank algorithms so they should all
produce the same answer when provided with zero or negative weights.
I don't recommend doing that but at least they are consistent
now...https://github.com/networkx/networkx/pull/1001

Aric

[Denzil Correa]

Hi Aric,

Can I know "how" the algorithm handles negative weights?

You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/Ut-i37vG2Dg/unsubscribe.
To unsubscribe from this group and all its topics, send an email to networkx-discu...@googlegroups.com.

To post to this group, send email to networkx...@googlegroups.com.
Visit this group at http://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/groups/opt_out.

--

Regards,

Denzil

http://correa.in

[Aric Hagberg]

When creating the 'Google Matrix' out of the input matrix (the
weighted adjacency matrix of the graph) the rows are divided by the
row sum unless it is zero (then the entire row is set to zero). That
sum might be negative. This was previously done differently in the
three different pagerank algorithms.
You could certainly argue that doing it this way is a bad idea and we
should instead check for negative weight values and raise an error.

If the resulting matrix still ends up with negative entries then the
Perron-Frobenius theorem doesn't apply
http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem and you
are not guaranteed to have a unique largest eigenvalue with positive
valued eigenvector.

Aric

[Denzil Correa]

Hi Aric,

Thanks for the reply. Do you think that it would make more sense to introduce a new link analysis algorithm like PageTrust to account for negative links? [0]

In the current setting, it seems "Garbage-In, Garbage-Out".

[0] http://perso.uclouvain.be/paul.vandooren/publications/deKerchoveV08b.pdf