k-Truss 分解之分散式演算法

Abstract

k-truss 是一種可以代表一個網路凝聚力大小的子圖，是在分析一個 社群網路的重要指標。然而，隨著巨量社群網路的出現，其構成的圖 會擁有百萬甚至上億個節點和邊，這導致k-truss 傳統單機版演算法所 需要的運算時間將會超乎想像的久；除此之外，如此大型的圖會無法 載入單一機器的記憶體，這也是另一個傳統演算法無法運作的原因。 目前，大資料的運算已經迫切的仰賴雲端運算，因此我們的目標是基 於雲端運算的框架上，設計出可以處理巨量資料的k-truss 演算法。在 本篇論文中，我們先就已經存在的MapReduce 版k-truss 演算法進行改 良。而由於MapReduce 的架構在處理分散式的圖運算時會因為太多的 迴圈而導致過多的IO 負載，我們轉而使用圖平行架構(graph-parallel anstractions) ，且提出一系列的理論基礎來設計一個k-truss 平行化演 算法的版本。實驗的結果顯示，從運算時間以及硬碟使用量的觀點來 看，我們基於圖平行架構所提出的k-truss 平行化演算法比其他基於 MapReduce 設計的版本來的更有效率。

k-truss, a type of cohesive subgraphs of a network, is an important measure for a social network graph. However, with the emergence of large online social networks, the running time of the traditional batch algorithms for k-truss decomposition is usually prohibitively long on such a graph with billions of edges and millions of vertices. Moreover, the size of a graph becomes too large to load into the main memory of a single machine. Currently, cloud computing has become an imperative way to process the big data. Thus, our aim is to design a scalable algorithm of k-truss decomposition in the scenario of cloud computing. In this thesis, we first improve the existing distributed k-truss decomposition in the MapReduce framework. We then propose a series of theoretical basis for k-truss and use them to design an algorithm based on graph-parallel abstractions. Our experiment results show that our method in the graph-parallel abstraction significantly outperforms the methods based on MapReduce in terms of running time and disk usage.