Python: Wie kann man die Anzahl aller möglichen kürzesten Pfade optimieren?

Question

In einem 3x3 Netzwerk möchte ich in der Lage sein, alle kürzesten Wege zwischen zwei beliebigen Knoten zu bestimmen. Dann möchte ich für jeden Knoten im Netzwerk berechnen, wie viele kürzeste Pfade einen bestimmten Knoten durchlaufen.

Dies erfordert die Verwendung der nx.all_shortest_paths(G,source,target)-Funktion, die eine generator zurückgibt. Dies steht im Gegensatz zur Verwendung der nx.all_pairs_shortest_path(G), wie vorgeschlagen here. Der Unterschied besteht darin, dass im ersten Fall die Funktion alle die kürzesten Pfade zwischen zwei beliebigen Knoten berechnet, während sie im letzteren Fall nur einen kürzesten Pfad zwischen demselben Knotenpaar berechnet.

Vorausgesetzt, dass ich alle kürzesten Wege berücksichtigen muss, habe ich das folgende Skript erstellt. Dies ist, wie ich das Netzwerk generieren Ich arbeite mit:

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) 

Und das ist, wie ich alle kürzesten Pfade zwischen zwei beliebigen Knoten drucken:

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

Das Ergebnis ist ein Weg vom Knoten x zu Knoten y, der nur die Knoten auf dem Weg enthält. Ein Auszug von dem, was ich bekommen ist:

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... 

Meine Frage: wie ich der letzte Codeblock ändern könnte, um sicherzustellen, dass ich weiß, wie viele kürzesten Wege, die insgesamt durch die einzelnen Knoten passieren? Gemäß dem von mir angegebenen Auszugsergebnis wird Knoten 1 zweimal durchlaufen, während Knoten 3 einmal durchlaufen wird (Start- und Endknoten sind ausgeschlossen). Diese Berechnung muss bis zum Ende ausgeführt werden, um die endgültige Anzahl von Pfaden durch jeden Knoten herauszufinden.

Answer 1

Ich würde vorschlagen, eine dict Mapping jeden Knoten auf 0

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

machen und dann für jeden Pfad finden Sie - sind Sie bereits zu finden, und das Drucken sie alle - durchlaufen die Eckpunkte auf dem Weg Inkrementieren die entsprechenden Werte in Ihrem dict:

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

Answer 2

Was Sie suchen, ist die nicht normalisierte betweenness centrality zu berechnen.

Von Wikipedia:

Die Between Zentralität ist ein Indikator für die Zentralität des Knotens in einem Netzwerk. Es ist gleich der Anzahl der kürzesten Pfade von allen Knoten zu allen anderen, die durch diesen Knoten gehen.

Allgemeiner, ich schlage vor, dass Sie sich alle standard measures of centrality already in Networkx ansehen.