TL/DR:Betweenness centrality is een erg langzame berekening, dus je wilt waarschijnlijk een benaderende maat gebruiken door een subset van myk te beschouwen. knooppunten waar myk is een getal dat veel kleiner is dan het aantal knooppunten in het netwerk, maar groot genoeg om statistisch zinvol te zijn (NetworkX heeft hiervoor een optie:betweenness_centrality(G, k=myk) .
Het verbaast me helemaal niet dat het lang duurt. Betweenness centrality is een langzame berekening. Het algoritme dat door networkx wordt gebruikt is O(VE) waar V is het aantal hoekpunten en E het aantal randen. In jouw geval VE = 10^13 . Ik verwacht dat het importeren van de grafiek O(V+E) . kost tijd, dus als dat lang genoeg duurt om te zien dat het niet onmiddellijk is, dan O(VE) zal pijnlijk zijn.
Als een kleiner netwerk met 1% van de knooppunten en 1% van de randen (dus 20.000 knooppunten en 50.000 randen) tijd X zou kosten, dan zou uw gewenste berekening 10000X kosten. Als X één seconde is, dan is de nieuwe berekening bijna 3 uur, wat volgens mij ongelooflijk optimistisch is (zie mijn test hieronder). Dus voordat u besluit dat er iets mis is met uw code, voert u deze uit op enkele kleinere netwerken en krijgt u een schatting van wat de runtime voor uw netwerk zou moeten zijn.
Een goed alternatief is om een benaderende maat te gebruiken. De standaard betweenness-maatstaf houdt rekening met elk afzonderlijk paar knooppunten en de paden ertussen. Networkx biedt een alternatief dat een willekeurige steekproef van slechts k . gebruikt knooppunten en vindt vervolgens de kortste paden tussen die k knooppunten en alle andere knooppunten in het netwerk. Ik denk dat dit een versnelling zou moeten geven om te draaien in O(kE) tijd
Dus wat je zou gebruiken is
betweenness_centrality(G, k=k)
Als u grenzen wilt hebben aan hoe nauwkeurig uw resultaat is, kunt u verschillende aanroepen doen met een kleine waarde van k , zorg ervoor dat ze relatief dicht bij elkaar liggen en neem dan het gemiddelde resultaat.
Hier zijn enkele van mijn snelle tests van runtime, met willekeurige grafieken van (V,E)=(20,50); (200.500); en (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
Dus op mijn computer duurt het 15 seconden om een netwerk af te handelen dat 0,1% zo groot is als dat van jou. Het zou ongeveer 15 miljoen seconden duren om een netwerk van dezelfde grootte als het uwe te maken. Dat is 1,5*10^7 seconden, iets minder dan de helft van pi*10^7 seconden. Aangezien pi*10^7 seconden een ongelooflijk goede benadering is van het aantal seconden in een jaar, zou mijn computer ongeveer 6 maanden nodig hebben.
U wilt dus met een benaderend algoritme werken.