Python：すべての可能な最短パスの数を最適化する方法は？

Question

3x3ネットワークでは、任意の2つのノード間の最短経路をすべて調べる必要があります。次に、ネットワーク内の各ノードについて、特定の1つのノードを通過する最短パスの数を計算します。

nx.all_shortest_paths(G,source,target)関数を使用する必要があります。これはgeneratorを返します。これはnx.all_pairs_shortest_path(G)を使用した場合とは異なり、hereとして示唆されています。相違点は、前者の場合、関数はすべてを2つのノード間の最短経路で計算し、後者の場合はを計算します。同じノード対の最短経路はです。

すべての最短経路を考えれば、私は次のスクリプトを思いついた。これは私が私が働いているネットワークを生成する方法である：

import networkx as nx 
N=3 
G=nx.grid_2d_graph(N,N) 
pos = dict((n, n) for n in G.nodes()) 
labels = dict(((i, j), i + (N-1-j) * N) for i, j in G.nodes()) 
nx.relabel_nodes(G,labels,False) 
inds=labels.keys() 
vals=labels.values() 
inds.sort() 
vals.sort() 
pos2=dict(zip(vals,inds)) 
nx.draw_networkx(G, pos=pos2, with_labels=False, node_size = 15) 

そして、これは私が任意の2つのノード間のすべての最短経路を印刷する方法である：

for n in G.nodes(): 
    for j in G.nodes(): 
     if (n!=j): #Self-loops are excluded 
      gener=nx.all_shortest_paths(G,source=n,target=j) 
      print('From node '+str(n)+' to '+str(j)) 
      for p in gener: 
       print(p) 
      print('------') 

結果はノードxからのパスです途中のノードのみを含むノードy。私は何を得るの抜粋です：

From node 0 to 2 #Only one path exists 
[0, 1, 2] #Node 1 is passed through while going from node 0 to node 2 
------ 
From node 0 to 4 #Two paths exist 
[0, 1, 4] #Node 1 is passed through while going from node 0 to node 4 
[0, 3, 4] #Node 3 is passed through while going from node 0 to node 4 
------ 
...continues until all pairs of nodes are covered... 

私の質問：どのように私は合計で、各ノードを通過するどのように多くの最短経路、知っていることを確認するために、最後のコードブロックを修正するだろうか？私が提供した抜粋の結果によると、ノード1は2回通過し、ノード3は1回通過する（開始ノードと終了ノードは除外される）。この計算は、各ノードを通る最終パス数を把握するために最後まで実行する必要があります。あなたは既に発見し、それらすべてを印刷している - - インクリメントパス上の頂点を反復処理を

Answer 1

私は、あなたが見つける各パスのため0

counts = {} 
for n in G.nodes(): counts[n] = 0 

へとdictのマッピングに、各ノードを作成することをお勧めあなたの辞書に適切な値：

# ... 
for p in gener: 
    print(p) 
    for v in p: counts[v] += 1 

Answer 2

何を計算しようとすると、正規化されていないbetweenness centralityです。 Wikipediaから

：

媒介中心は、ネットワーク内のノードの中心性の指標です。これは、すべての頂点からそのノードを通過する他のすべての頂点までの最短経路の数に等しい。

さらに一般的には、standard measures of centrality already in Networkxをすべてご覧ください。