有效的方式來操縱大（不適合內存）圖

Question

我需要維護一個大的有向圖G，可能有數百萬個節點和邊。可能它可能不適合內存。

一些頻繁操作我需要在該曲線圖中執行包括：

1. 每個節點/邊緣將具有與其相關聯的用戶定義的屬性，諸如訪問計數，體重等

2. 對於每個節點（頂點），我需要根據屬性值執行有效的查詢。例如，找到X值大於v1但小於v2的節點。這可能需要在某些領域建立索引。

3. 我需要找到一個給定節點的所有入邊和出邊，並更新邊的權重。我需要從給定節點進行本地（基於DFS的）遍歷，並返回滿足特定用戶定義謂詞的所有路徑（此謂詞可以使用路徑中節點/邊的屬性值）。

4. 我將需要有效地添加/刪除節點/邊緣。雖然這並不像操作1,2,3那樣頻繁。

圖中有一些熱點可能比其他部分更頻繁地訪問，我想將這些熱點緩存在內存中。

以最少的實施工作實現這一目標的有效方法是什麼？

我在看一些基於磁盤的圖形數據庫，例如Neo4j/InfiniteGraph/DEX。儘管它們支持上述所有操作，但它似乎是一種矯枉過正，因爲我不需要它們提供的很多功能，例如一致性/併發控制或基於羣集的複製。另外，它們中的很多都基於Java，我更喜歡C/C++接口。

基本上我只需要一個磁盤圖形庫，它可以有效地處理持久性，查詢節點和本地遍歷。你可以使用現有的（開源）項目嗎？如果不是，那麼實施這樣的事情的最好方法是什麼？

Answer 1

既然你「喜歡的東西用C/C++接口」，你可能想給GraphChi一試。

「GraphChi可以通過使用一種新穎的算法用於從磁盤（SSD或硬盤驅動器）處理的圖形只運行在一臺機器上非常大的圖形的計算。」

GraphChi爲C++的源代碼和文檔可在Google Code project pages。

的Example Apps包括算法例如PageRank，社區檢測和連接組件。您可能可以修改這些以適應您的需求。

Answer 2

另一個選項可以是e4Graph，這是一個簡單的C++圖形持久性庫。我沒有嘗試過，但它看起來很有希望。

Answer 3

我看過一些有數百萬節點的大圖。我推薦的是你找到一個點，你應該做一個加權壓縮。因此，您將採用N個節點，使用平均值和權重壓縮到N/M個節點，然後重新構建圖形。

您將在每個如此多的節點之後重新進行重新壓縮。原因在於，隨着時間的推移，所有事物都會變得巨大，從某種意義上說，你將能夠正常化它。

你有一個有向圖。當你在較大的節點上傳遞更大的數據時，你可以這樣說，如果A> B>（E & D）> H，你可以這樣說：A> H。

它確實允許您基於節點之間的最短跳轉來確定節點之間的公共路由。如果它不在壓縮列表中，它至少會朝某個區域前進，並且可以根據某種意義解壓縮。

Answer 4

如果您尋找C++解決方案，GraphLab可能是一個不錯的選擇。但它是一個分佈式計算解決方案。因爲你處理了數百萬個節點/邊緣。這可能是一個很好的選擇。本文列出了一些其他的圖形庫：

http://www.ibm.com/developerworks/library/os-giraph/