TL/DR:बीच की केंद्रीयता एक बहुत धीमी गणना है, इसलिए आप शायद myk के सबसेट पर विचार करके एक अनुमानित माप का उपयोग करना चाहते हैं। नोड्स जहां myk कुछ संख्या नेटवर्क में नोड्स की संख्या से बहुत कम है, लेकिन सांख्यिकीय रूप से सार्थक होने के लिए पर्याप्त है (नेटवर्कएक्स के पास इसके लिए एक विकल्प है:betweenness_centrality(G, k=myk) ।
मुझे आश्चर्य नहीं है कि इसमें लंबा समय लग रहा है। बीच की केंद्रीयता एक धीमी गणना है। नेटवर्कएक्स द्वारा उपयोग किया जाने वाला एल्गोरिथम O(VE) . है जहां V शीर्षों की संख्या है और E किनारों की संख्या। आपके मामले में VE = 10^13 . मैं O(V+E) . लेने के लिए ग्राफ़ आयात करने की अपेक्षा करता हूं समय, इसलिए यदि इसमें इतना समय लग रहा है कि आप बता सकते हैं कि यह तात्कालिक नहीं है, तो O(VE) दर्दनाक होने वाला है।
यदि 1% नोड्स और 1% किनारों (इसलिए 20,000 नोड्स और 50,000 किनारों) के साथ एक कम नेटवर्क में समय X लगेगा, तो आपकी वांछित गणना में 10000X लगेंगे। यदि एक्स एक सेकंड है, तो नई गणना 3 घंटे के करीब है, जो मुझे लगता है कि अविश्वसनीय रूप से आशावादी है (नीचे मेरा परीक्षण देखें)। इसलिए इससे पहले कि आप तय करें कि आपके कोड में कुछ गड़बड़ है, इसे कुछ छोटे नेटवर्क पर चलाएं और अनुमान लगाएं कि आपके नेटवर्क के लिए रन टाइम कितना होना चाहिए।
एक अच्छा विकल्प अनुमानित माप का उपयोग करना है। मानक बीच माप हर एक जोड़ी नोड्स और उनके बीच के रास्तों पर विचार करता है। Networkx एक विकल्प प्रदान करता है जो केवल k . के यादृच्छिक नमूने का उपयोग करता है नोड्स और फिर उन k . के बीच सबसे छोटा पथ ढूंढता है नेटवर्क में नोड्स और अन्य सभी नोड्स। मुझे लगता है कि यह O(kE) . में चलने के लिए एक स्पीडअप देना चाहिए समय
तो आप जो उपयोग करेंगे वह है
betweenness_centrality(G, k=k)
यदि आप चाहते हैं कि आपका परिणाम कितना सही है, इस पर सीमाएं हों, तो आप k के छोटे मान के साथ कई कॉल कर सकते हैं। , सुनिश्चित करें कि वे अपेक्षाकृत करीब हैं और फिर औसत परिणाम लें।
(V,E)=(20,50); (200,500); और (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
तो मेरे कंप्यूटर पर एक नेटवर्क को संभालने में 15 सेकंड लगते हैं जो आपके आकार का 0.1% है। आपके जैसे आकार के नेटवर्क को करने में लगभग 15 मिलियन सेकंड का समय लगेगा। वह 1.5*10^7 सेकेंड है जो कि pi*10^7 सेकेंड के आधे से थोड़ा कम है। चूंकि pi*10^7 सेकंड एक वर्ष में सेकंड की संख्या के लिए एक अविश्वसनीय रूप से अच्छा अनुमान है, इसमें मेरे कंप्यूटर को लगभग 6 महीने लगेंगे।
तो आप एक अनुमानित एल्गोरिथम के साथ चलना चाहेंगे।
