2

我正在使用 NetworkX 库来处理一些中小型未加权、无符号、有向图,这些图表示 Web 2.0 站点的使用情况(最小的图:不到两打节点,最大的:几千个)。我要计算的一件事是特征向量中心性,如下所示:

>>> eig = networkx.eigenvector_centrality(my_graph)
>>> eigs = [(v,k) for k,v in eig.iteritems()]
>>> eigs.sort()
>>> eigs.reverse() 

但是,这会产生意想不到的结果:具有 0 出度但从非常中心的节点接收向内弧的节点出现在具有 0.0 特征向量中心度的列表的最后(不是数学家,我可能对此感到困惑,但我不认为向外的弧应该对节点对有向图的中心性有任何影响)。在调查这些结果的过程中,我从文档中注意到 NetworkX 默认计算“正确的”特征向量中心性;出于好奇,我决定通过推荐的方法计算“左”特征向量中心性,即在计算特征向量中心性之前反转图形(参见 Networkx 文档)。令我惊讶的是,我得到了完全相同的结果:每个节点都被计算为具有与以前完全相同的特征向量中心性。我认为这应该是一个非常不可能的结果(参见 Wikipedia 文章),但我已经用我正在使用的所有图表复制了它。谁能向我解释我做错了什么?

注意:使用 PageRank 算法的 NetworkX 实现提供了我所期望的结果,即从非常中心的节点接收向内弧的节点即使出度为 0 也具有高中心性。PageRank 通常被认为是特征向量中心性的变体(参见维基百科文章)。

编辑:根据 Aric 的请求,我已经包含了一些数据。这是我最小的图表的匿名版本。(如果问题特定于我的图表结构,我无法发布玩具数据。)在我的机器上运行下面的代码(使用 Python 2.7)似乎显示(a)每个节点的左右特征向量中心性是相同,并且 (b) 出度为 0 的节点也总是具有特征向量中心性 0,即使它们在整个图形中非常中心(例如节点 61)。

import networkx

anon_e_list = [(10, 59), (10, 15), (10, 61), (15, 32), (16, 31), (16, 0), (16, 37), (16, 54), (16, 45), (16, 56), (16, 10), (16, 8), (16, 36), (16, 24), (16, 30), (18, 34), (18, 36), (18, 30), (19, 1), (19, 3), (19, 51), (19, 21), (19, 40), (19, 41), (19, 30), (19, 14), (19, 61), (21, 64), (26, 1), (31, 1), (31, 3), (31, 51), (31, 62), (31, 33), (31, 40), (31, 23), (31, 30), (31, 18), (31, 13), (31, 46), (31, 61), (32, 3), (32, 2), (32, 33), (32, 6), (32, 7), (32, 9), (32, 15), (32, 17), (32, 18), (32, 23), (32, 30), (32, 5), (32, 27), (32, 34), (32, 35), (32, 38), (32, 40), (32, 42), (32, 43), (32, 46), (32, 47), (32, 62), (32, 56), (32, 57), (32, 59), (32, 64), (32, 61), (33, 0), (33, 31), (33, 2), (33, 7), (33, 9), (33, 10), (33, 12), (33, 64), (33, 14), (33, 46), (33, 16), (33, 17), (33, 18), (33, 19), (33, 20), (33, 21), (33, 22), (33, 23), (33, 30), (33, 26), (33, 28), (33, 11), (33, 34), (33, 32), (33, 35), (33, 37), (33, 38), (33, 39), (33, 41), (33, 43), (33, 45), (33, 24), (33, 47), (33, 48), (33, 49), (33, 58), (33, 62), (33, 53), (33, 54), (33, 55), (33, 60), (33, 57), (33, 59), (33, 5), (33, 52), (33, 63), (33, 61), (34, 58), (34, 4), (34, 33), (34, 20), (34, 55), (34, 28), (34, 11), (34, 64), (35, 18), (35, 60), (35, 61), (37, 34), (37, 48), (37, 49), (37, 18), (37, 33), (37, 39), (37, 21), (37, 42), (37, 26), (37, 59), (37, 44), (37, 12), (37, 11), (37, 61), (41, 3), (41, 50), (41, 18), (41, 52), (41, 33), (41, 54), (41, 19), (41, 22), (41, 5), (41, 46), (41, 25), (41, 44), (41, 13), (41, 62), (41, 29), (44, 32), (44, 3), (44, 18), (44, 33), (44, 40), (44, 41), (44, 30), (44, 23), (44, 61), (50, 17), (50, 37), (50, 62), (50, 41), (50, 25), (50, 43), (50, 27), (50, 28), (50, 29), (54, 33), (54, 41), (54, 10), (54, 59), (54, 63), (54, 61), (58, 62), (58, 46), (59, 31), (59, 34), (59, 30), (59, 49), (59, 18), (59, 33), (59, 9), (59, 10), (59, 8), (59, 13), (59, 24), (59, 61), (60, 34), (60, 16), (60, 35), (60, 50), (60, 4), (60, 6), (60, 59), (60, 24), (63, 40), (63, 33), (63, 30), (63, 61), (63, 53)]

my_graph = networkx.DiGraph()
my_graph.add_edges_from(anon_e_list)
r_eig = networkx.eigenvector_centrality(my_graph)
my_graph2 = my_graph.reverse()
l_eig = networkx.eigenvector_centrality(my_graph2)

for nd in my_graph.nodes():
    print 'node: {} indegree: {} outdegree: {} right eig: {} left eig: {}'.format(nd,my_graph.in_degree(nd),my_graph.out_degree(nd),r_eig[nd],l_eig[nd])
4

1 回答 1

4

这两行

my_graph2 = my_graph.copy()
my_graph2.reverse()

应该替换为

my_graph2 = my_graph.reverse()

因为 reverse() 方法默认返回图形的副本。

于 2013-01-31T13:46:10.923 回答