python - networkx - weight in betwenness 和 current flow betweenness 的含义

Question

我正在使用 Python Networkx 2.1 在具有加权边的无向图上计算介数中心性和当前流介数中心性。我关心的是 networkx 函数中参数“weight”的含义。请考虑以下示例给出的图表

G= nx.Graph()
G.add_path([1, 2,4])
G.add_path([1, 3,4])
G[1][2]['weight'] = 20
G[1][3]['weight'] = 1
G[2][4]['weight'] = 1
G[3][4]['weight'] = 1

for u,v,d in G.edges(data=True):
    if 'weight' in d:
        if d['weight'] != 0:
            d['reciprocal'] = 1/d['weight']

在我的例子中，边缘权重是关系的强度，因此是积极的东西。这个想法是，具有较高权重的边应该对介数有更大的贡献。考虑到这个想法，我说计算节点加权介数中心性和加权电流介数中心性的正确公式如下是否正确？

b = nx.betweenness_centrality(G, weight= 'reciprocal', normalized=False)
Out[46]: {1: 1.0, 2: 1.0, 3: 0.0, 4: 0.0}

f = nx.current_flow_betweenness_centrality(G, normalized= False, weight= 'weight', solver='lu')
Out[48]: 
{1: 1.3114754098360655,
 2: 1.3114754098360657,
 3: 0.6885245901639343,
 4: 0.6885245901639347}

请注意，在第一个公式中，我使用了边缘权重的倒数，因为我觉得这些被算法解释为距离，所以有些“不好”。另一方面，在第二个公式中，我使用了原始权重，因为在电流介数算法中，这似乎更重视节点 1 和 2，就像介于两者之间。因此这里的权重似乎是“正”的。

我想知道我是否做错了什么。事实上，在较大的图表上，如果我使用相同的权重参数而不是倒数，则两个度量的相关性更高。这两种算法如何处理权重？

Answer 1

这可能对你现在没有太大帮助，但对于其他有同样问题的人......

查看源代码表明，如果提供权重，Dijkstra 算法用于计算最短路径。 Dijkstra 算法通常将权重视为距离(即“坏”)，此实现也不异常(exception)。因此，取边缘权重的倒数是正确的方法。我不确定你所说的“在更大的图表上，这两个指标更相关”是什么意思。这将取决于您的大图彼此之间的相似程度。

源代码:https://networkx.github.io/documentation/latest/_modules/networkx/algorithms/centrality/betweenness.html