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()

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

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

我可以用

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

现在我只想将键/值对保留在标签为例如“A”的位置。因此，我可以关注具有相同标签的节点。我希望它不是抽象的，但你有什么想法吗？

提前谢谢。

Answer 1

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

这返回一个节点列表，我们可以使用它来获得所有组合的最短路径。

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')

[out]：

1.5

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