Networkx

Question

我有一个有向图，有481个节点和6817条边（权重是边出现的次数，否则大约有400万条边）。图表显示在这里：

我想找到大多数时候从最外层节点进入到图中心的路径（也许是总体权重最高的路径？）。我已经计算了节点的特征向量中心性并排在前 20 名。那些节点是出现在中心的节点。我尝试了什么：

d = g.successors(top20nodes[0])
h = g.subgraph(d)

这是一种仅获取最终在本例中具有最高特征向量中心性的节点处结束的节点的方法。但是，我不知道如何获得通向该节点的 n 条出现次数最多（权重最大）的路径。

理想情况下我的最终结果是这样的，灰色节点只是为了表明我只对 n 条出现次数最多的路径感兴趣。在这种情况下，那 4 条通往中心的红色路径：

我不一定要寻找确切的代码，我只是不知道如何从这里开始。有人知道如何实现这一目标吗？

Answer 1

请注意，我的解决方案并非完全最优，在某些情况下它可能 return 不是最佳路径

我想出了一个算法给你。它有几个假设，所以它不是最好的。不过应该return效果不错

首先，你应该定义你的图形中心（我把它放在我的算法之外）。定义它后，您应该将所有中心节点替换为只有一个 - 主中心节点（不要忘记边缘）。之后，我的算法开始。

它从具有定义深度的中心节点开始BFS树。这是主要的不完美部分：如果在两个节点之间有两条路径 - 长重和短光，将选择短光。我不确定它是否对你的图表很重要，但看起来不会（图片提供的信息不多）。

BFS树构建完成后，会汇总所有BFS路径的权重并进行排序。然后你可以只选择前X个路径。

希望能帮到您解决问题:)

import networkx as nx

# Create graph
G = nx.DiGraph()
G.add_nodes_from([1,6,7,8,9,10,11,12,13,14,15,16,17])
G.add_weighted_edges_from([
    (6,1,2),
    (7,1,5),
    (10,1,7),
    (12,1,1),
    (15,1,4),
    (17,1,6),
    (8,6,5),
    (8,7,8),
    (9,8,2),
    (11,10,1),
    (13,12,5),
    (14,13,6),
    (16,15,3),
    (16,14,4),
    (14,16,1),
])

# Get the BFS tree. 1 is the center, 100 is the BFS length. Note, that
# long lengths MAY waste a lot of computing time
B = nx.bfs_tree(G, 1, 100)
# Get our center
root = list(v for v, d in B.in_degree() if d == 0)[0]
# Get all leaves _in_BFS_tree
leaves = (v for v, d in B.out_degree() if d == 0)
# Get all paths
all_paths = [nx.shortest_path(B, root, l) for l in leaves]
# Get all sorted pairs [path, path_length]
result = sorted(
    [
        (
            path, sum((G.edges[path[i+1], path[i]]['weight'])
            for i in range(len(path) - 1))
        )
        for path in all_paths
    ],
    key=lambda x: x[1],
    reverse=True
)

result
[([1, 12, 13, 14], 12),
 ([1, 6, 8, 9], 9),
 ([1, 10, 11], 8),
 ([1, 15, 16], 7),
 ([1, 17], 6),
 ([1, 7], 5)]

Networkx - 找到加权网络中出现次数最多的路径

Networkx - find the most appearing paths in weighted network

python

graph-theory