Skip to main content
 首页 » 编程设计

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

2024年11月24日13telwanggs

我有一个有向图,有 481 个节点和 6817 条边(权重是边出现的次数,否则大约有 400 万条边)。该图显示在这里:

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

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

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

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

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

请您参考如下方法:

请注意,我的解决方案并非完全最优,在某些情况下它可能会返回非最佳路径

我为你想出了一个算法。它有几个假设,所以它不是最好的。但它应该会返回相当不错的结果。

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

它从具有定义深度的中心节点开始 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)]