TL/DR:Sentralitas antara adalah perhitungan yang sangat lambat, jadi Anda mungkin ingin menggunakan ukuran perkiraan dengan mempertimbangkan subset dari myk node di mana myk adalah beberapa angka yang jauh lebih sedikit daripada jumlah node dalam jaringan, tetapi cukup besar untuk bermakna secara statistik (NetworkX memiliki opsi untuk ini:betweenness_centrality(G, k=myk) .
Saya sama sekali tidak terkejut itu memakan waktu lama. Sentralitas antara adalah perhitungan yang lambat. Algoritma yang digunakan oleh networkx adalah O(VE) dimana V adalah jumlah simpul dan E jumlah tepi. Dalam kasus Anda VE = 10^13 . Saya berharap mengimpor grafik akan mengambil O(V+E) waktu, jadi jika itu memakan waktu cukup lama sehingga Anda dapat mengatakan itu tidak instan, maka O(VE) akan menyakitkan.
Jika jaringan yang dikurangi dengan 1% dari node dan 1% dari tepi (jadi 20.000 node dan 50.000 tepi) akan memakan waktu X, maka perhitungan yang Anda inginkan akan memakan waktu 10000X. Jika X adalah satu detik, maka perhitungan baru mendekati 3 jam, yang menurut saya sangat optimis (lihat pengujian saya di bawah). Jadi sebelum Anda memutuskan ada yang salah dengan kode Anda, jalankan di beberapa jaringan yang lebih kecil dan dapatkan perkiraan waktu berjalan untuk jaringan Anda.
Alternatif yang baik adalah dengan menggunakan ukuran perkiraan. Ukuran antara standar mempertimbangkan setiap pasangan node dan jalur di antara mereka. Networkx menawarkan alternatif yang menggunakan sampel acak hanya k node dan kemudian menemukan jalur terpendek antara k node dan semua node lain dalam jaringan. Saya pikir ini akan memberikan percepatan untuk dijalankan di O(kE) waktu
Jadi yang akan Anda gunakan adalah
betweenness_centrality(G, k=k)
Jika Anda ingin membatasi seberapa akurat hasil Anda, Anda dapat melakukan beberapa panggilan dengan nilai k yang lebih kecil. , pastikan bahwa mereka relatif dekat dan kemudian ambil hasil rata-rata.
Berikut adalah beberapa pengujian run time saya, dengan grafik acak (V,E)=(20,50); (200.500); dan (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
Jadi di komputer saya, dibutuhkan 15 detik untuk menangani jaringan yang besarnya 0,1% dari jaringan Anda. Ini akan memakan waktu sekitar 15 juta detik untuk melakukan jaringan dengan ukuran yang sama seperti milik Anda. Itu 1,5*10^7 detik yang sedikit di bawah setengah dari pi*10^7 detik. Karena pi*10^7 detik adalah perkiraan yang sangat bagus untuk jumlah detik dalam setahun, komputer saya membutuhkan waktu sekitar 6 bulan.
Jadi, Anda ingin menjalankan dengan algoritme perkiraan.
