NetworkX有哪些可擴展性問題？

我對有數百萬節點和數千萬條邊的大型網絡的網絡分析感興趣。我希望能夠做許多事情，比如解析來自多種格式的網絡，查找連接的組件，檢測社區，以及運行像PageRank這樣的中心度量。NetworkX有哪些可擴展性問題？

我被NetworkX吸引，因爲它有一個很好的API，很好的文檔，並且多年來一直處於積極的發展階段。另外，因爲它是在python中，它應該很快與開發。

在最近的一次演講（幻燈片都可以在GitHub上here），有人聲稱：

不像許多其他工具，NX設計來處理有關問題，現代規模數據.. NX中的大多數核心算法都依賴於極快的遺留代碼。

該演示文稿還指出，NetworkX的基本算法是在C/Fortran中實現的。

但是，看看源代碼，它看起來像NetworkX主要是用python編寫的。我對源代碼並不太熟悉，但我知道有幾個例子，其中NetworkX使用numpy來完成繁重的任務（反過來使用C/Fortran來完成線性代數）。例如，文件networkx/networkx/algorithms/centrality/eigenvector.py使用numpy來計算特徵向量。

有沒有人知道是否這種調用像numpy這樣的優化庫的策略在整個NetworkX中都非常流行，或者只有幾種算法可以實現呢？任何人都可以描述與NetworkX相關的其他可擴展性問題嗎？從NetworkX首席程序員

回覆我提出的NetworkX郵件列表上的這個問題，ARIC哈格伯格回答說：

在NetworkX使用的數據結構適合擴展到大問題（例如，數據結構是一個鄰接表）。算法具有不同的縮放屬性，但您提到的一些可用（例如，PageRank，連接的組件，在邊數量上是線性的）。

此時NetworkX是純Python代碼。使用Python字典對鄰接結構進行編碼，以犧牲內存和計算速度爲代價提供了很大的靈活性。大型圖將佔用大量的內存，你最終會用完。

NetworkX確實使用NumPy和SciPy來計算基於線性代數的主要爲的算法。在那種情況下，使用NumPy矩陣或稀疏矩陣將該圖表表示爲（複製）爲鄰接矩陣。這些算法可以受益於在NumPy和SciPY中引用的遺留C和FORTRAN代碼。

來源

2011-11-02 conradlee

看來我目前無法親自檢查源代碼。但無論如何，請考慮：80％的時間可能花費在20％的代碼中。 Mercurial主要是用Python編寫的，但我沒有聽說過一個人抱怨它的速度與Git相比，它主要是C. – delnan

是的，但我也擔心內存。 networkx中的圖形表示是一個python庫。這是否意味着我只能將較小的圖形放入內存？ – conradlee

你的大問題將是記憶。 Python只需就可以不用來處理數千萬個對象，而無需在你的類實現中跳過箍筋。許多對象的內存開銷太高，達到2GB，32位代碼無法工作。有辦法解決它 - 使用插槽，陣列或numpy。它應該是好的，因爲networkx是爲性能編寫的，但如果有幾件事情不起作用，我會檢查你的內存使用情況。對於縮放，算法基本上是唯一與圖形有關的事情。如果圖形算法做錯了，圖形算法往往會有很大的擴展性，並且它們可能會像其他任何語言一樣在Python中完成。

來源

2011-11-02 12:01:53 wisty

networkX主要用python編寫的事實並不意味着它不可擴展，也不要求完美。總是有一個權衡。如果您在「機器」上投入更多資金，您將擁有更多的可擴展性，以及使用pythonic圖庫的好處。

如果不是，也有其他的解決方案，（here和here），它可以消耗較少的內存（基準看，我想的igraph完全ç支持，因此會），但你可能會錯過NX的Python的感覺。

來源

2011-11-02 11:22:01 hymloth

這部分地回答了我的問題。但我也想知道，如所聲稱的，NetworkX的許多「核心」算法是否在C/Fortran中實現。 – conradlee

我調查了一下（當前）源代碼，並且沒有發現C/Fortran實現。似乎在那裏的一切都是純python ... – hymloth

謝謝你看看。請記住，如果調用numpy，那麼numpy可能會使用LAPACK或其他優化的線性代數包（取決於系統配置）。我不太瞭解NetworkX實際使用numpy的頻率（這是我的問題），但我知道一些例子。例如，在networkx/networkx/algorithms/centrality/eigenvector.py中使用numpy來查找特徵向量。 – conradlee

這是一個老問題，但我認爲值得一提的是graph-tool具有與NetworkX非常相似的功能，但它在C++中使用模板（使用Boost Graph Library）實現，因此速度更快（up to two orders of magnitude ）並使用更少的內存。

免責聲明：我圖形工具的作者。

來源

2013-05-04 22:34:15

我試過圖形工具。它確實速度更快，但使用起來很難看。 API不會覺得pythonic。 –

真的......只是想和我這裏的人分享我的經驗。 –

@TiagoPeixoto - 您的庫適合處理〜3M節點和〜10M邊緣嗎？我猜測存儲器只是內存，對嗎？ – Avision

NetworkX有哪些可擴展性問題？

回答

相關問題