TL / DR:Độ trung tâm giữa là một phép tính rất chậm, vì vậy bạn có thể muốn sử dụng một số đo gần đúng bằng cách xem xét một tập hợp con của myk các nút mà myk là một số ít hơn nhiều so với số nút trong mạng, nhưng đủ lớn để có ý nghĩa về mặt thống kê (NetworkX có một tùy chọn cho điều này:betweenness_centrality(G, k=myk) .
Tôi không ngạc nhiên chút nào vì nó mất nhiều thời gian. Tính trung tâm giữa là một phép tính chậm. Thuật toán được networkx sử dụng là O(VE) ở đâu V là số đỉnh và E số lượng các cạnh. Trong trường hợp của bạn VE = 10^13 . Tôi mong đợi quá trình nhập biểu đồ sẽ lấy O(V+E) thời gian, vì vậy nếu thời gian đó đủ lâu để bạn có thể biết nó không phải là tức thời, thì hãy O(VE) sẽ rất đau đớn.
Nếu một mạng giảm với 1% số nút và 1% số cạnh (vì vậy 20.000 nút và 50.000 cạnh) sẽ mất thời gian X, thì phép tính mong muốn của bạn sẽ mất 10000X. Nếu X là một giây, thì phép tính mới là gần 3 giờ, mà tôi nghĩ là cực kỳ lạc quan (xem thử nghiệm của tôi bên dưới). Vì vậy, trước khi bạn quyết định có điều gì đó không ổn với mã của mình, hãy chạy mã đó trên một số mạng nhỏ hơn và ước tính thời gian chạy sẽ dành cho mạng của bạn.
Một giải pháp thay thế tốt là sử dụng một số đo gần đúng. Tiêu chuẩn đo lường độ giữa xem xét mọi cặp nút và đường dẫn giữa chúng. Networkx cung cấp một giải pháp thay thế sử dụng một mẫu ngẫu nhiên chỉ k và sau đó tìm các đường dẫn ngắn nhất giữa các k đó các nút và tất cả các nút khác trong mạng. Tôi nghĩ điều này sẽ tăng tốc độ chạy trong O(kE) thời gian
Vì vậy, những gì bạn sẽ sử dụng là
betweenness_centrality(G, k=k)
Nếu bạn muốn có giới hạn về mức độ chính xác của kết quả, bạn có thể thực hiện một số lệnh gọi với giá trị nhỏ là k , hãy đảm bảo rằng chúng tương đối gần nhau và sau đó lấy kết quả trung bình.
Đây là một số thử nghiệm nhanh của tôi về thời gian chạy, với đồ thị ngẫu nhiên là (V, E) =(20,50); (200.500); và (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
Vì vậy, trên máy tính của tôi, mất 15 giây để xử lý mạng có kích thước 0,1% so với mạng của bạn. Sẽ mất khoảng 15 triệu giây để tạo một mạng có cùng kích thước với mạng của bạn. Đó là 1,5 * 10 ^ 7 giây, nhỏ hơn một nửa số pi * 10 ^ 7 giây. Vì pi * 10 ^ 7 giây là một con số gần đúng cực kỳ tốt cho số giây trong một năm, điều này sẽ khiến máy tính của tôi mất khoảng 6 tháng.
Vì vậy, bạn sẽ muốn chạy với một thuật toán gần đúng.
