为什么我应该在计算接近中心性之前反转 Networkx 有向图的弧线？
Why should I reverse the arc of a Networkx DiGraph before calculating closeness centrality?
我在 Networkx 库中注意到了这种奇怪的行为，这（至少对我而言）有点出乎意料。
在下面的示例中，我创建了一个包含 4 个节点的有向图，其中每个节点仅与其后继节点相连。我希望节点 4（可以从 1、2 和 3 到达）应该具有最高的中心性，但我得到一些不同的东西。
pd=nx.DiGraph()
pd.add_edges_from([(0,1),(1,2),(2,3),(3,4)])
nx.closeness_centrality(pd)
{0: 0.4, 1: 0.375, 2: 0.3333333333333333, 3: 0.25, 4: 0.0}
为了得到我期望的结果，我应该 .reverse() 图表。
为什么？
如果你检查 documentation 它说：
Closeness centrality of a node u is the reciprocal of the sum of the shortest path distances from u to all n−1 other nodes. Since the sum of distances depends on the number of nodes in the graph, closeness is normalized by the sum of minimum possible distances n−1. [emphasis mine]
你的节点4没有从它到其他节点的路径，只是从其他节点到它。
考虑到两个方向的路径的合理定义是取 closeness_centrality 结果的倒数和 .reverse() 上 closeness_centrality 结果的倒数图形，将它们相加然后取倒数（注意 0 值）。您会看到的一个问题是，如果一对 u 和 v 在它们之间没有定向路径，则两者的最终中心性均为 0。
另一种选择涉及定义中心性，以便对于每对节点 u 和 v，您可以在任一方向上取最短路径的距离。我认为这将涉及重写算法。您可以通过文档找到当前算法，其中有一个link 来源（它是here）。不是特别复杂，所以我觉得是可行的。
我在 Networkx 库中注意到了这种奇怪的行为，这（至少对我而言）有点出乎意料。 在下面的示例中，我创建了一个包含 4 个节点的有向图，其中每个节点仅与其后继节点相连。我希望节点 4（可以从 1、2 和 3 到达）应该具有最高的中心性，但我得到一些不同的东西。
pd=nx.DiGraph()
pd.add_edges_from([(0,1),(1,2),(2,3),(3,4)])
nx.closeness_centrality(pd)
{0: 0.4, 1: 0.375, 2: 0.3333333333333333, 3: 0.25, 4: 0.0}
为了得到我期望的结果，我应该 .reverse() 图表。
为什么？
如果你检查 documentation 它说：
Closeness centrality of a node u is the reciprocal of the sum of the shortest path distances from u to all n−1 other nodes. Since the sum of distances depends on the number of nodes in the graph, closeness is normalized by the sum of minimum possible distances n−1. [emphasis mine]
你的节点4没有从它到其他节点的路径，只是从其他节点到它。
考虑到两个方向的路径的合理定义是取 closeness_centrality 结果的倒数和 .reverse() 上 closeness_centrality 结果的倒数图形，将它们相加然后取倒数（注意 0 值）。您会看到的一个问题是，如果一对 u 和 v 在它们之间没有定向路径，则两者的最终中心性均为 0。
另一种选择涉及定义中心性，以便对于每对节点 u 和 v，您可以在任一方向上取最短路径的距离。我认为这将涉及重写算法。您可以通过文档找到当前算法，其中有一个link 来源（它是here）。不是特别复杂，所以我觉得是可行的。