在Big Graph上實現算法的最佳方法

我們知道，我們可以在圖上使用鄰接表或鄰接矩陣來表示算法。對於小圖很容易和直接。但是當圖形很大時，比如社交網絡圖，那麼實現傳統算法如最短路徑查找的數據結構應該是最好的。鄰接矩陣或列表將無法工作，因爲高內存要求，對嗎？社交網絡引擎使用什麼方法？在Big Graph上實現算法的最佳方法

鄰接列表在空間複雜度（至少漸近地）方面有點優化。你可以期望的最好的方法是用一些不變的因子用簡潔的表示來達到它的效果 –

@NiklasB。，我想OP會詢問關於ram中任何單個數據結構都太大而不適合的圖，比如圖Facebook上的朋友。 –

@CodieCodeMonkey誰說什麼關於RAM？我說的也適用，如果你把圖形存儲在磁盤上。我想「鄰接列表將不起作用，因爲高內存要求」是一個我想解決的錯誤概念 –

鄰接列表正在我找到的源中使用。對於非常大的數據大小，您最終可能會將數據保存在磁盤上或使用多臺機器來解決問題 - 因此我建議將「外部存儲器」或Hadoop等關鍵字添加到搜索中。我嘗試添加Hadoop和發現了一些文件上經由並行廣度優先搜索解決單源最短路徑 - http://www.cs.kent.edu/~jin/Cloud12Spring/GraphAlgorithms.pptx，http://courses.cs.washington.edu/courses/cse490h/08au/lectures/algorithms.pdf，Hadoop MapReduce implementation of shortest PATH in a graph, not just the distance

此外，http://researcher.watson.ibm.com/researcher/files/us-heq/Large%20Scale%20Graph%20Processing%20with%20Apache%20Giraph.pdf不覆蓋最短路徑，但是使用層解決連接部件的一個有趣的例子在Hadoop之上，這可能會讓生活更輕鬆。

2014-04-01 05:15:03 mcdowella

回答