3

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

  • pagerank(G)向我抛出 ZeroDivsionError

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

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

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

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

NetworkX 版本 - 1.8.1 Python - 2.7

4

2 回答 2

4

@mtitan8 的回答很好，但还有更多内容。

自您提出原始问题以来，NetworkX 代码已被修改，因此当权重为零或负数时，pagerank()、pagerank_numpy() 和 pagerank_scipy() 都会给出相同的答案（https://github.com/networkx/networkx /拉/1001 )

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

如果生成的矩阵仍然以负条目结束，则 Perron-Frobenius 定理不适用 http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem并且不能保证您具有唯一的最大特征值具有正值特征向量。

于 2013-11-12T23:58:46.663 回答
2

pagerankstochastic_graph失败，因为它使用--like pagerank_numpyor执行计算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 次迭代后没有收敛，但这是另一个问题。

于 2013-11-05T20:00:15.557 回答