Networkx 带标签的平均最短路径

Question

我想计算标记图中具有相同标记的节点的平均最短路径。例如，红色标记为 A，黑色标记为 B。

G = nx.DiGraph()
G.add_node('A', label = 'A')
G.add_node('B', label = 'B')
G.add_node('C', label = 'A')
G.add_node('D', label = 'B')
G.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A')])
H = G.to_undirected()

现在我只想计算 A 的平均最短路径，基于此

V_m 是具有相同标签的顶点。 n_{i,j} 是最短路径的数量， d_{i,j} 是测地距离。

我想使用 Networkx 来实现它。开始使用节点属性进行标记。

我可以用

读出带有标签的节点

graph_labels = (nx.get_node_attributes(G, 'label'))

现在我只想将 key/value 对保留在标签所在的位置，例如"A"。所以我可以专注于具有相同标签的节点。我希望它不是抽象的，但你有什么想法吗？

提前致谢。

Answer 1

Select 个标签节点

def select_nodes_by_label(G, lab):
    return [node[0] for node in G.nodes(data='label') if node[1] == lab ]

这个returns我们可以用来获取所有组合的最短路径的节点列表。

from itertools import combinations

def avg_shortest_path_labeled_node(G, lab):
    sel_nodes = select_nodes_by_label(G,lab)
    V_m = len(sel_nodes)

    # collect all lengths of shortest paths from combinations of labeled nodes 
    sp_len = [len(nx.shortest_path(G,c[0], c[1]))  for c in combinations(sel_nodes,2)]
    n = len(sp_len)
    return sum(sp_len)/(n) * 1/(V_m * (V_m - 1))

测试

avg_shortest_path_labeled_node(G,'A')

[输出]:

1.5

这是你期待的结果吗？在更复杂的图形上测试此函数可能会很有趣。

Networkx 带标签的平均最短路径

Networkx Average shortest path with labels

python

shortest-path

networkx

Select 个标签节点

测试