Tôi quan tâm đến phân tích mạng trên các mạng lớn với hàng triệu nút và hàng chục triệu cạnh. Tôi muốn có thể làm những việc như phân tích các mạng từ nhiều định dạng, tìm các thành phần được kết nối, phát hiện cộng đồng và chạy các thước đo trọng tâm như PageRank.Các vấn đề về khả năng mở rộng nào được liên kết với NetworkX?
Tôi bị thu hút bởi NetworkX bởi vì nó có một api tốt đẹp, tài liệu tốt và đã được phát triển tích cực trong nhiều năm. Plus vì nó nằm trong python, nên nhanh chóng phát triển.
Trong một bài thuyết trình gần đây (các slide có sẵn trên github here), người ta khẳng định rằng:
Không giống như nhiều công cụ khác, NX được thiết kế để xử lý dữ liệu trên thang điểm từ liên quan đến vấn đề hiện đại .. Hầu hết các thuật toán cốt lõi trong NX dựa vào mã di sản cực nhanh.
Bản trình bày cũng nêu rõ rằng thuật toán cơ bản của NetworkX được triển khai trong C/Fortran.
Tuy nhiên, nhìn vào mã nguồn, có vẻ như NetworkX chủ yếu được viết bằng python. Tôi không quá quen thuộc với mã nguồn, nhưng tôi nhận thức được một vài ví dụ mà NetworkX sử dụng numpy để làm việc nâng hạng nặng (mà lần lượt sử dụng C/Fortran để làm đại số tuyến tính). Ví dụ, tập tin networkx/networkx/algorithms/centrality/eigenvector.py sử dụng numpy để tính toán eigenvectors.
Có ai biết nếu chiến lược này gọi một thư viện được tối ưu hóa như numpy thực sự phổ biến trong suốt NetworkX hay chỉ một vài thuật toán làm điều đó? Ngoài ra, bất cứ ai cũng có thể mô tả các vấn đề khả năng mở rộng khác liên quan đến NetworkX?
Trả lời từ NetworkX Chì Programmer tôi đặt ra câu hỏi này trên mailing list NetworkX, và Aric Hagberg trả lời:
Các cấu trúc dữ liệu được sử dụng trong NetworkX phù hợp với mở rộng quy mô để vấn đề lớn (ví dụ như cấu trúc dữ liệu là một danh sách kề). Thuật toán có các thuộc tính chia tỷ lệ khác nhau nhưng một số thuộc tính mà bạn đề cập có thể sử dụng được (ví dụ: PageRank, các thành phần được kết nối, là tuyến tính số phức tạp về số cạnh).
Tại thời điểm này NetworkX là mã Python thuần túy. Cấu trúc kề được mã hóa bằng các từ điển Python cung cấp tính linh hoạt tuyệt vời với chi phí bộ nhớ và tốc độ tính toán. Các đồ thị lớn sẽ mất rất nhiều bộ nhớ và cuối cùng bạn sẽ hết.
NetworkX sử dụng NumPy và SciPy cho các thuật toán chủ yếu là dựa trên đại số tuyến tính. Trong trường hợp đó, biểu đồ được biểu diễn (được sao chép) dưới dạng ma trận kề bằng cách sử dụng ma trận NumPy hoặc SciPy ma trận thưa thớt. Những thuật toán này có thể được hưởng lợi từ mã C và FORTRAN cũ được sử dụng dưới mui xe trong NumPy và SciPY.
Có vẻ như tôi gặp sự cố khi tự kiểm tra nguồn tại thời điểm này. Nhưng trong mọi trường hợp, hãy xem xét: 80% thời gian có thể được chi tiêu bằng 20% mã. Mercurial được viết * chủ yếu * bằng Python, nhưng tôi chưa từng nghe một người phàn nàn về tốc độ của nó so với Git, chủ yếu là C. – delnan
Vâng, nhưng tôi cũng lo lắng về trí nhớ. Biểu diễn biểu đồ trong networkx là một thư viện python. Điều đó có nghĩa là tôi chỉ có thể phù hợp với các đồ thị nhỏ hơn vào bộ nhớ? – conradlee