NetworkX：Dijkstra 的最短路径与 Brandes 算法的中介中心性
NetworkX: Djikstra's shortest path vs Brandes algorithm for betweeness centrality
我有几个 Python 计算各种网络度量的脚本。
给定一个图 (G)，第一个脚本计算从每个节点到所有其他节点的平均最短路径，并将其存储在 Nx1 矩阵 (L) 中。来自 NetworkX Python 库的 Djikstra 算法的实现用于此：
for i in range(num_nodes):
for j in range(num_nodes):
dj_path_matrix[i,j] = nx.dijkstra_path_length(G, i, j)
L = np.sum(dj_path_matrix, axis=0)/(num_nodes - 1)
给定相同的图 (G)，第二个脚本使用 NetworkX 库中 Brande 算法的实现来计算介数中心性并将其存储在 Nx1 矩阵 (BC) 中：
BC = nx.betweenness_centrality(G, normalized=True)
我的问题是：为什么计算 L 比计算 BC 花费的时间长得多？
按照我的理解，节点的 BC 是衡量最短路径通过该节点的频率。因此，要计算 BC，您肯定需要计算图中所有可能的最短路径。当然，BC 应该至少和 L 一样长？使用我的脚本，给定同一张图，计算 BC 需要几秒钟，但计算 L 最多需要半小时。
如果我要求您找到从给定节点 u 到图中每个其他节点的最短路径，您可能不会选择此处提供的技术。如果我们同时计算所有这些路径长度，就有可能更有效地计算它们。我们找到所有长度为 1 的路径。然后我们找到所有长度为 2 的路径，这些路径不会重新访问先前找到的节点。然后所有长度为3的路径，等等
这比计算从 u 到一个节点的路径，然后重新开始并找到到下一个节点的路径要高效得多。介数中心性是通过立即找到 u 和 G 中所有节点之间的所有最短路径而不是按顺序找到每个节点来计算的。
我有几个 Python 计算各种网络度量的脚本。
给定一个图 (G)，第一个脚本计算从每个节点到所有其他节点的平均最短路径，并将其存储在 Nx1 矩阵 (L) 中。来自 NetworkX Python 库的 Djikstra 算法的实现用于此：
for i in range(num_nodes):
for j in range(num_nodes):
dj_path_matrix[i,j] = nx.dijkstra_path_length(G, i, j)
L = np.sum(dj_path_matrix, axis=0)/(num_nodes - 1)
给定相同的图 (G)，第二个脚本使用 NetworkX 库中 Brande 算法的实现来计算介数中心性并将其存储在 Nx1 矩阵 (BC) 中：
BC = nx.betweenness_centrality(G, normalized=True)
我的问题是：为什么计算 L 比计算 BC 花费的时间长得多？
按照我的理解，节点的 BC 是衡量最短路径通过该节点的频率。因此，要计算 BC，您肯定需要计算图中所有可能的最短路径。当然，BC 应该至少和 L 一样长？使用我的脚本，给定同一张图，计算 BC 需要几秒钟，但计算 L 最多需要半小时。
如果我要求您找到从给定节点 u 到图中每个其他节点的最短路径，您可能不会选择此处提供的技术。如果我们同时计算所有这些路径长度，就有可能更有效地计算它们。我们找到所有长度为 1 的路径。然后我们找到所有长度为 2 的路径，这些路径不会重新访问先前找到的节点。然后所有长度为3的路径，等等
这比计算从 u 到一个节点的路径，然后重新开始并找到到下一个节点的路径要高效得多。介数中心性是通过立即找到 u 和 G 中所有节点之间的所有最短路径而不是按顺序找到每个节点来计算的。