社群網路生成及最大團問題於MapReduce有效率的演算法

Efficient MapReduce-based Algorithm for Social Network Generation and Finding Maximal Clique

羅亦辰(Yi-Chen Lo)

指導教授 ： 林守德

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.10500

摘要

社群網路生成在社群網路分析領域是一個重要的問題。人工產生的隨機圖被用來模擬真實世界社群網路已經行之有年。隨著真實世界社群網路如Twitter, Facebook等快速膨脹，我們需要可以產生大規模隨機圖的方法。Google提出的MapReduce[1]運算架構提供了我們將社群網路生成演算法平行化的需要及儲存大型網路檔案的分散式檔案系統。這篇論文提出將BA model[5]當中preferential attachment機制用到的degree由實際值代換成期望值，藉此讓BA model的生成過程可以被獨立地分割利於平行化。我們以MapReduce做實驗的結果顯示我們設計的平行演算法有良好的可擴放性並且產生出來的圖保有BA model原本的特性如power-law degree分布。這篇論文也將由Sergei Vassilvitskii在XXL Graph Algorithms[9]提出數三角形問題中把高degree的點分開處理的想法應用到最大團問題的MapReduce演算法。實驗的結果顯示這個方法讓計算效率有明顯的改進。

關鍵字

MapReduce ； 平行運算 ； 圖探勘 ； BA模型 ； 最大團問題

並列摘要

Social network generation is an important problem in social network analysis. Artificially generated random graphs are used to model real world social networks for a long time. With the expanding size of real world social networks such as Twitter, Facebook, we need some methods to generate large scale random graphs. MapReduce[1] proposed by Google is the right framework to provide parallelism on social network generation algorithm and distributed file system to store large output graph data. In our paper we propose a method to replace the exact degree, which is used as the attachment preference in original BA model[5], with the expected value of degree. By this substitution BA model generation algorithm can be divided into several independent tasks to fit in parallel computing. And our experiment results on MapReduce shows that after this substitution, graphs generated by BA model keep their original properties such as power-law degree distribution with good scalability. In this paper we also apply the idea of differentiate high degree vertices in triangle counting algorithm proposed in XXL Graph Algorithms by Sergei Vassilvitskii[9], to finding maximal clique algorithm in MapReduce. As a result of our experiment, the computation efficiency is obviously improved.

並列關鍵字

MapReduce ； parallel computing ； graph mining ； BA model ； maximal clique problem

參考文獻

[1] J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” OSDI, 2004.

[4] D. Watts and S. Strogatz (1998): Collective dynamics of small-world networks. Nature, 363:202–204.

[5] R. Albert; A.-L. Barabási (2002). “Statistical mechanics of complex networks”. Reviews of Modern Physics 74: 47–97.

[6] Bron, Coen; Kerbosch, Joep (1973), “Algorithm 457: finding all cliques of an undirected graph”, Commun. ACM (ACM) 16 (9): 575–577

[7] U. Kang, C. E. Tsourakakis, and C. Faloutsos. Pegasus: A peta-scale graph mining system. Data Mining, IEEE International Conference on, 0:229–238, 2009.