NetworkX python :pagerank_numpy，pagerank失败，但pagerank_scipy工作

Question

我在加权DiGraph上运行PageRank，其中节点= 61634，边缘= 28,378。

• pagerank(G)扔给我零分错误

• pagerank_numpy(G)抛出我 ValueError ： 数组到大

• pagerank_scipy(G)给了我页面排名

我可以理解pagerank_numpy错误是由于内存限制造成的，但为什么页面排名失败？我尝试将无穷小的值添加到权重为零的边缘，但同样的问题仍然存在。一些指针会很好。

链接到我的 GraphML 文件 - https://mega.co.nz/#!xlYzEDAI!Lyh5pD-NJL61JPfkrNyJrEm0NnFc586A0MUD8OMYAO0

网络X 版本 - 1.8.1蟒蛇 - 2.7

Answer 1

@mtitan8的回答很好，但故事还有更多。

自您提出原始问题以来，NetworkX 代码已被修改，以便当权重为零或负时，pagerank_numpy（） 和 pagerank_scipy（） 都给出相同的答案 （https://github.com/networkx/networkx/pull/1001）

当您具有负权重时，这些函数产生的结果可能不是您想要的（如果它有效的话）。 算法现在处理从输入矩阵（图形的加权邻接矩阵）中创建"谷歌矩阵"的方式是，行除以行总和，除非它为零（然后整行设置为零）。 这个总和可能是负数。

如果生成的矩阵仍然以负条目结束，则佩伦-弗罗贝尼乌斯定理不适用http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem 和你不保证具有唯一的最大特征值和正值特征向量。

Answer 2

pagerank失败，因为它使用 stochastic_graph 执行计算 - 与 pagerank_numpy 或 pagerank_scipy 不同。从文档中，stochastic_graph需要：

NetworkX 图形必须具有有效的边权重

这个"有效的边缘权重"点（根本没有解释，我认为这是一个错误）是你问题的根源。

对于有向图，stochastic_graph使用每个节点的out_degree来规范化边。再次来自文档：

[out] 度数是与节点相邻的边权重的总和。

因此，当您的边权重为零或负权重时，归一化过程会中断，并出现ZeroDivisionError。负权重是一个问题的原因是它们可以抵消正权重，从而使节点度数为零。例如，在您的图形中，节点'2123271'有两个边，其权重之和为 0：

>>> G.edges('2123271', data=True)
[('2123271', '1712899', {'weight': -1L}),
 ('2123271', '890839', {'weight': 1L})]

将图形中的负边权重或零边权重替换为较小的正边权重，使其pagerank可以运行：

In [1]: import networkx as nx
In [2]: G = nx.read_graphml("your_graph.graphml")
In [3]: defaultEdgeWeight = 0.01
In [4]: for u, v, d in G.edges(data=True):
            if d['weight'] <= 0:
                G[u][v]['weight'] = defaultEdgeWeight
In [5]: P = nx.pagerank( G )

当然，pagerank在 102 次迭代后并没有收敛，但这是另一个问题。