分佈式本地聚類係數算法（MapReduce/Hadoop）

我已經實現了基於local clustering coefficient algorithm的MapReduce範例。然而，對於較大的數據集或特定數據集（節點的高平均度），我遇到了嚴重的麻煩。我試圖調整我的hadoop平臺和代碼，但結果並不令人滿意（至少可以這麼說）。不，我已將注意力轉移到實際改變/改進算法。下面是我目前的算法（僞代碼）分佈式本地聚類係數算法（MapReduce/Hadoop）

foreach(Node in Graph) { 
    //Job1 
    /* Transform edge-based input dataset to node-based dataset */ 

    //Job2 
    map() { 
    emit(this.Node, this.Node.neighbours) //emit myself data to all my neighbours 
    emit(this.Node, this.Node) //emit myself to myself 
    } 

    reduce() { 
    NodeNeighbourhood nodeNeighbourhood; 
    while(values.hasNext) { 
     if(myself) 
     this.nodeNeighbourhood.setCentralNode(values.next) //store myself data 
     else 
     this.nodeNeighbourhood.addNeighbour(values.next) //store neighbour data 
    } 

    emit(null, this.nodeNeighbourhood) 
    } 

    //Job3 
    map() { 
    float lcc = calculateLocalCC(this.nodeNeighbourhood) 
    emit(0, lcc) //emit all lcc to specific key, combiners are used 
    } 

    reduce() { 
    float combinedLCC; 
    int numberOfNodes; 
    while(values.hasNext) { 
     combinedLCC += values.next; 
    } 

    emit(null, combinedLCC/numberOfNodes); // store graph average local clustering coefficient 
    } 
}

稍微詳細瞭解一下代碼。對於有向圖，鄰居數據被限制爲節點ID和出口邊緣目的地ID（以減小數據大小），用於無向其節點ID和邊緣目的地ID。排序和合並緩衝區增加到1.5 Gb，合併流80.

可以清楚地看到，Job2是整個算法的實際問題。它產生大量的數據，必須進行排序/複製/合併。這基本上殺死了我的算法對於某些數據集的性能。有人可以指導我如何改進算法（我正在考慮創建一個迭代Job2 [在每次迭代中只處理N個M節點，直到每個節點都被「處理」），但現在我已經放棄了這個想法）。在我看來，應該減少Job2映射輸出，以避免代價高昂的排序/合併進程，從而導致性能下降。

我也爲Giraph平臺實現了相同的算法（3個工作以及相同的「通信」模式，也是「Job2」問題）。然而，Giraph是一個內存平臺，相同的「問題」數據集的算法會導致OutOfMemoryException。

對於任何評論，評論，指導方針，我將不勝感激。

UPDATE

我要去改變算法「大大」。我發現這篇文章Counting Triangles。

代碼實現後，我會發表我的意見在這裏和更詳細的代碼（如果這種方法會成功）。

UPDATE_2

在我已經結束「修改」 NodeIterator ++算法，以我的需求（雅虎紙可通過在文章中的鏈接）結束。不幸的是，雖然我能看到表現有所改善，但最終的結果並不如我所希望的那麼好。我得出的結論是，我可以得到的集羣太小，無法對這些特定數據集進行LCC計算。所以這個問題仍然存在，或者說它會發展。是否有人知道用於計算LCC或三角形資源有限的高效分佈式/順序算法？（絕不意味着我說的NodeIterator ++算法是壞的，我簡單地說，我可用的資源是不夠的）。

來源

2012-06-10 alien01

只是在黑暗中拍攝..你有沒有嘗試[mahout的集羣作業]（https://builds.apache.org/job/Mahout-Quality/javadoc/org/apache/mahout/graph/common/LocalClusteringCoefficientJob.html ） –

不，我會研究一下。 Thx小費。 – alien01

你能解決它嗎？ Job2的reduce（）發出什麼？ –

在論文「用於大規模圖算法的MPI中的MapReduce」中，作者很好地描述了三角形計數的MapReduce實現。該論文可在此獲得：http://www.sciencedirect.com/science/article/pii/S0167819111000172，但您可能需要一個帳戶才能訪問論文。（我在一個支付訂閱費用的大學系統中，所以我從來不知道我只能訪問它，因爲他們已經付款了。）作者可能會在個人網站上發佈論文草稿。

還有另一種方法可以計算三角形 - 可能效率會低得多，除非您的圖形相當密集。首先，構造圖的鄰接矩陣A，然後計算A^3（可以很容易地並行執行矩陣乘法）。然後，總結A^3的（i，i）條目並將答案除以6.這將給出三角形的數量，因爲A^k的i，j條目計算從i到k的長度k的數量到j，因爲我們只看長度爲3的散步，任何從i開始並在3步後結束於i的行走都是一個三角形......過度計數爲6。這主要是效率較低，因爲矩陣的大小如果你的圖很稀疏的話，與邊界列表的大小相比將會非常大。

來源

2014-11-04 21:44:54 TravisJ

分佈式本地聚類係數算法（MapReduce/Hadoop）

回答

相關問題