Ich habe einen einfachen Twitter-Benutzer-Graphen mit ungefähr 2 Millionen Knoten und 5 Millionen Kanten. Ich versuche mit Centrality herumzuspielen. Die Berechnung dauert jedoch sehr lange (mehr als eine Stunde). Ich betrachte meine Grafik nicht als sehr groß, also vermute ich, dass etwas mit meinem Code nicht stimmt.
Hier ist mein Code.
%Vor%Die Daten befinden sich in MongoDB. Hier ist das Beispiel der Daten.
%Vor%Ich habe versucht, die Betweenness-Zentralität parallel zur Beschleunigung zu verwenden, aber es ist immer noch super langsam. Ссылка
%Vor%Der Importvorgang von Mongodb zu networkx ist relativ schnell, weniger als eine Minute.
TL / DR: Die Betweenness-Zentralität ist eine sehr langsame Berechnung. Daher möchten Sie wahrscheinlich ein ungefähres Maß verwenden, indem Sie eine Untermenge von myk -Knoten betrachten, wobei myk eine Nummer ist, 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 lange dauert. Die Betweenness Centrality ist eine langsame Berechnung. Der von networkx verwendete Algorithmus ist O(VE) , wobei V die Anzahl der Scheitelpunkte und E die Anzahl der Kanten ist. In deinem Fall VE = 10^13 . Ich erwarte, dass das Importieren des Diagramms O(V+E) time dauert. Wenn das also lange genug dauert, um zu erkennen, dass es nicht sofort erfolgt, wird O(VE) 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 liegt die neue Berechnung nahe bei 3 Stunden, was ich unglaublich optimistisch finde (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 schätzen Sie die Laufzeit für Ihr Netzwerk ein.
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, die eine zufällige Stichprobe von nur k Knoten verwendet und dann die kürzesten Pfade zwischen diesen k Knoten und allen anderen Knoten im Netzwerk findet. Ich denke, das sollte eine Beschleunigung in O(kE) time
Also, was Sie verwenden würden, ist
%Vor% Wenn Sie wissen wollen, wie genau Ihr Ergebnis ist, können Sie mehrere Aufrufe mit einem kleineren Wert von k machen, stellen Sie sicher, dass sie relativ nah sind und nehmen Sie dann das Durchschnittsergebnis.
Hier sind einige meiner schnellen Tests der Laufzeit, mit zufälligen Graphen von (V, E) = (20,50); (200,500); und (2000,5000)
%Vor%Also dauert es auf meinem Computer 15 Sekunden, um ein Netzwerk zu bearbeiten, das 0,1% der Größe von Ihnen ist. Es würde ungefähr 15 Millionen Sekunden dauern, ein Netzwerk der gleichen Größe wie Ihres zu machen. 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 ist, würde dies meinen Computer etwa 6 Monate dauern.
Sie wollen also mit einem ungefähren Algorithmus arbeiten.