如何計算多個節點未連接的多向圖中的平均最短路徑長度？

我想計算我的多向圖average_shortest_path_length但沒有與其它節點如何計算多個節點未連接的多向圖中的平均最短路徑長度？

例如我有節點和如下面邊緣網絡連接的節點：

lst_nodes=[2782, 27118, 28931, 28936, 43162, 28770, 48325, 33783] 

lst_edge = [(28931, 28936L), (28931, 27118L), (28931, 27118L), (28931, 33783L), (48325, 28936L), (28936, 43162L), 
      (28936, 48325L), (27118, 28936L), (27118, 28936L), (27118, 48325L), (43162, 48325L), (2782, 28931L), 
      (2782, 48325L), (2782, 48325L), (2782, 27118L), (2782, 33783L)] 

MDG = nx.MultiDiGraph() 
MDG.add_nodes_from(lst_nodes) 
MDG.add_edges_from(lst_edge) 

print 'avg shortest path length:', nx.average_shortest_path_length(MDG)

它會結束了與像

networkx.exception.NetworkXError: Graph is not connected.

異常

但根據筆記NetworkX

For disconnected graphs you can compute the average shortest path length for each component: >>> G=nx.Graph([(1,2),(3,4)]) >>> for g in nx.connected_component_subgraphs(G): ... print(nx.average_shortest_path_length(g)) 1.0 1.0

它應該與組件的工作原理，所以我儘量代碼

for g in nx.connected_component_subgraphs(MDG): 
    print nx.average_shortest_path_length(g)

之前，但如果我刪除了與像然而 networkx.exception.NetworkXNotImplemented: not implemented for directed type 異常結束我可以計算網絡的平均最短路徑長度，所以我想知道如何計算多個節點未連接的多向圖中的平均最短路徑長度？

來源

2017-03-07 LancelotHolmes

可以將每個組件的轉換爲無向圖：'用於nx.connected_component_subgraphs（G）G：F = NX。圖（克）; ...' – DyZ

@DYZ很好，這不正確，首先，有向圖和無向圖的平均最短路徑長度是不同的，我嘗試了你的解決方案，最終會出現一個新的異常'ZeroDivisionError ：由於網絡中存在單個節點，因此被零除法。無論如何感謝 – LancelotHolmes

你是對的，對於有向圖和無向圖，平均最短路徑是不同的。但'nx.average_shortest_path_length'只適用於無向圖（這就是爲什麼會引發異常），所以我猜你沒有選擇。當然，你可以計算'nx.shortest_path_length'並取平均值。 – DyZ

事實上，我認爲nx.shortest_path_length是最合理的解決方案：

import statistics 
from itertools import chain 
# This includes the isolated node! 
path_lengths = (x.values() for x in nx.shortest_path_length(MDG).values()) 
statistics.mean(chain.from_iterable(path_lengths)) 
# 1

來源

2017-03-07 03:15:43 DyZ

謝謝@DYZ，但根據[Wikipedia]（https://en.wikipedia.org/wiki/Average_path_length），平均最短路徑長度不計算爲簡單平均值，但我不知道我是否應該除以節點總數（'/ 8 *（8-1）'）或者僅僅是節點數（'/ 7 *（7-1）'），而後者得到2/3的結果我發現如果我把它看作一個無向圖，那麼計算結果應該除以組件中的節點數，其結果大約爲1.47，類似於'Gephi'中的結果 – LancelotHolmes

如何計算多個節點未連接的多向圖中的平均最短路徑長度？

回答

相關問題