Networkx beendet die Berechnung der Betweenness-Zentralität für 2 Millionen Knoten nie

TL/DR:Betweenness Centrality ist eine sehr langsame Berechnung, daher möchten Sie wahrscheinlich ein ungefähres Maß verwenden, indem Sie eine Teilmenge von myk berücksichtigen Knoten, bei denen myk ist eine Zahl, die viel kleiner ist als die Anzahl der Knoten im Netzwerk, aber groß genug, um statistisch aussagekräftig zu sein (NetworkX hat eine Option dafür:betweenness_centrality(G, k=myk)). .

Ich bin überhaupt nicht überrascht, dass es so lange dauert. Betweenness Centrality ist eine langsame Berechnung. Der von networkx verwendete Algorithmus ist O(VE) wobei V ist die Anzahl der Scheitelpunkte und E die Anzahl der Kanten. In Ihrem Fall VE = 10^13 . Ich erwarte, dass das Importieren des Diagramms O(V+E) dauert Zeit, also wenn das lange genug dauert, dass Sie sagen können, dass es nicht sofort erfolgt, dann O(VE) wird schmerzhaft sein.

Wenn ein reduziertes Netzwerk mit 1 % der Knoten und 1 % der Kanten (also 20.000 Knoten und 50.000 Kanten) Zeit X benötigen würde, würde Ihre gewünschte Berechnung 10000X dauern. Wenn X eine Sekunde ist, dann beträgt die neue Berechnung fast 3 Stunden, was ich für unglaublich optimistisch halte (siehe meinen Test unten). Bevor Sie also entscheiden, dass etwas mit Ihrem Code nicht stimmt, führen Sie ihn in einigen kleineren Netzwerken aus und erhalten Sie eine Schätzung der Laufzeit für Ihr Netzwerk.

Eine gute Alternative ist die Verwendung eines ungefähren Maßes. Das Standard-Betweenness-Maß berücksichtigt jedes einzelne Knotenpaar und die Pfade zwischen ihnen. Networkx bietet eine Alternative an, die eine Zufallsstichprobe von nur k verwendet Knoten und findet dann die kürzesten Pfade zwischen diesen k Knoten und alle anderen Knoten im Netzwerk. Ich denke, das sollte die Ausführung in O(kE) beschleunigen Zeit

Was Sie also verwenden würden, ist

betweenness_centrality(G, k=k)

Wenn Sie Grenzen haben möchten, wie genau Ihr Ergebnis ist, können Sie mehrere Aufrufe mit einem kleineren Wert von k durchführen , vergewissern Sie sich, dass sie relativ nah beieinander liegen, und nehmen Sie dann das Durchschnittsergebnis.

Hier sind einige meiner Schnelltests zur Laufzeit mit zufälligen Diagrammen von (V,E)=(20,50); (200.500); und (2000,5000)

import time
for n in [20,200,2000]:
    G=nx.fast_gnp_random_graph(n, 5./n)
    current_time = time.time()
    a=nx.betweenness_centrality(G)
    print time.time()-current_time

>0.00247192382812
>0.133368968964
>15.5196769238

Auf meinem Computer dauert es also 15 Sekunden, um ein Netzwerk zu verarbeiten, das 0,1 % der Größe Ihres Netzwerks hat. Es würde ungefähr 15 Millionen Sekunden dauern, um ein Netzwerk der gleichen Größe wie Ihres zu erstellen. Das sind 1,5*10^7 Sekunden, was etwas weniger als die Hälfte von pi*10^7 Sekunden ist. Da pi*10^7 Sekunden eine unglaublich gute Annäherung an die Anzahl der Sekunden in einem Jahr sind, würde mein Computer dafür etwa 6 Monate brauchen.

Sie sollten also mit einem ungefähren Algorithmus arbeiten.