python - Networkx 和 Networkit 中的介数错误？

Question

显然，使用 networkx 和 networkit 计算的节点介数和边介数都给出了与预期不同的值。

让我们考虑以下无向图（这些 Lecture notes 中的第 20/85 页），写为边列表并保存在mygraph.txt：

1 2
1 5
2 3
2 5
3 4
4 5
4 6

节点介数应该是（这些讲义中的第 20/85 页）：

Node | Betweenness
1 0
2 1.5
3 1
4 4
5 3
6 0

但是，通过运行以下代码（我在 networkx 和 networkit 中使用G1和G2作为图形的不同名称，但它们是完全相同的图形，来自同一个文件mygraph.txt）：

import networkx as nx
from networkit import *  
import networkit as nk 


G1 = nx.read_edgelist("mygraph.txt",create_using=nx.Graph(), nodetype = int)
G1.number_of_nodes()

node_btw = nx.betweenness_centrality(G1, normalized=False)
edge_btw = nx.edge_betweenness_centrality(G1, k=None, normalized=False, weight=None, seed=None)

print('NETWORK-X')
print(node_btw.values())
print(edge_btw.values())


edgeListReader = nk.graphio.EdgeListReader(' ', 1)
G2 = nk.readGraph("/home/JohnRambo/Documents/myFolder/mygraph.txt", nk.Format.EdgeListTabOne)
print(G2.numberOfNodes(), G2.numberOfEdges()) 

G2.indexEdges()
btwn = nk.centrality.Betweenness(G2, normalized=False, computeEdgeCentrality=True)
btwn.run()

print('NETWORK-IT')
print(btwn.scores()[:10])
print(btwn.edgeScores()[:10])

我得到了这些结果（PS：我手动添加了文本node betweenness和edge betweenness）：

NETWORK-X
node betweenness: [0.0, 1.5, 3.0, 1.0, 4.5, 0.0]
edge betweenness: [2.0, 3.0, 3.5, 2.5, 5.5, 3.5, 5.0]

NETWORK-IT
node betweenness: [0.0, 3.0, 2.0, 9.0, 6.0, 0.0]
edge betweenness: [4.0, 7.0, 7.0, 6.0, 5.0, 11.0, 10.0]

我的计算给出了不同的结果（节点介数分数与这些讲义中第 20/85 页显示的分数一致）

node betweenness: [0.0, 1.5, 1.0, 4.5, 3.0, 0.0]
edge betweenness: [2.0, 3.0, 3.5, 2.5, 3.5, 5.5, 5.0]

您能否澄清一下并提出解决此问题的方法？

标签： pythonnetworkxgraph-theorynetworkit

Answer 1

正如 Kyle 在他的评论中提到的，网络中的节点是按照与边缘列表相关的顺序添加的。为了解决这个问题，一个简单的排序将解决它。第三行输出显示了实际的节点序列。

关于边，从文件中读取边列表时发生了一些意想不到的事情：边 (4, 5) 被加载为 (5, 4)。见第二行输出。这会导致边缘的预期排序顺序（就像文件一样）不同：第六个和第七个节点被交换。

下面的代码通过键值（节点号）对节点介数字典进行排序，同时将介数值放在一个元组中，在第四行输出。

最后几行显示每条边及其中间值。

import networkx as nx

G1 = nx.read_edgelist("mygraph.txt",create_using=nx.Graph(), nodetype = int)
G1.number_of_nodes()

node_btw = nx.betweenness_centrality(G1, normalized=False)
edge_btw = nx.edge_betweenness_centrality(G1, k=None, normalized=False, weight=None, seed=None)

print('NETWORK-X')
print(tuple(node_btw.keys()))
print(tuple(edge_btw.keys()))
nn_btw = tuple(v for _,v in sorted(node_btw.items(), key=lambda x: x[0]))
print(nn_btw)
en_btw = tuple(v for _,v in sorted(edge_btw.items(), key=lambda x: x[0]))
print(en_btw)
for k,v in sorted(edge_btw.items(),key=lambda x: x[0]):
    print(k, v)

输出：

# NETWORK-X
# (1, 2, 5, 3, 4, 6)
# ((1, 2), (1, 5), (2, 3), (2, 5), (5, 4), (3, 4), (4, 6))
# (0.0, 1.5, 1.0, 4.5, 3.0, 0.0)
# (2.0, 3.0, 3.5, 2.5, 3.5, 5.0, 5.5)
# (1, 2) 2.0
# (1, 5) 3.0
# (2, 3) 3.5
# (2, 5) 2.5
# (3, 4) 3.5
# (4, 6) 5.0
# (5, 4) 5.5