在Hadoop中存儲圖形進行計算的有效方法

Question

我目前正在嘗試在Hadoop的幫助下執行像聚類係數一樣的巨大圖表計算。因此，我需要一種有效的方式來存儲圖形，以便我可以輕鬆訪問節點，鄰居和鄰居的鄰居。該圖非常稀疏，並存儲在一個巨大的製表符分隔文件中，其中第一個字段是邊界轉到第二個字段中第二個節點的節點。

在此先感謝！

Answer 1

直接在HDFS中存儲圖形的問題是，您無法執行數據的隨機讀取。因此，要查找節點的所有鄰居，必須在HDFS中處理整個邊緣列表以查找連接到該節點的節點。

因此，要執行聚類係數計算，您需要將所有數據傳遞兩次。第一次找到連接到起始節點的節點。第二次瞭解這些節點是如何相互連接的。

每次你想在圖表中出現另一個級別時，你都需要處理整個圖表來找到新的連接。

這是一件容易的事情，很好，是的。時間效率高嗎？這實際上取決於你希望如何快速計算像LCC這樣的事情，以及你的圖表有多大。它不會接近實時。

另一種方法是使用HBase以某種方式存儲邊緣，這將使您能夠以並行方式隨機訪問節點。畢竟HBase是hadoop的一部分。

如果您想以平行方式存儲大圖，可能會感興趣的可能是FlockDB。它是Twitter最近發佈的分佈式圖形數據庫。我沒有使用它，但它可能值得一看。

Answer 2

如果您想以逐個用戶的身份執行此操作，HBase/Cassandra可能會工作。將邊緣存儲在列族中：user_a_id是行鍵，user_b_id是列鍵（具有空值）。 FlockDB不太適合（他們明確引用「圖形步行查詢」作爲非目標）

如果您希望計算整個圖中的聚類係數 - 也就是做一個巨人高效的計算 - 我會使用Hadoop。有一些注意事項（見下文），你可以很直接地做到這一點;在infochimps上，我們在具有數百萬個節點+邊的強鏈接twitter圖上使用了Wukong。

如果你的數據集有很高的偏差，那麼無效的做法是從每個節點天真地進行2跳廣度優先搜索。思考Twitter的後續圖表：跟隨@wholefoods的170萬人擁有60萬次外出邊緣，以爭奪1萬億2跳。使用強大的鏈接使得這更容易（大大減少了歪斜）;否則，做一些局部聚類並迭代。