請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56335
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳銘憲(Ming-Syan Chen) | |
dc.contributor.author | Pei-Ling Chen | en |
dc.contributor.author | 陳姵伶 | zh_TW |
dc.date.accessioned | 2021-06-16T05:23:58Z | - |
dc.date.available | 2014-08-21 | |
dc.date.copyright | 2014-08-21 | |
dc.date.issued | 2014 | |
dc.date.submitted | 2014-08-15 | |
dc.identifier.citation | [1] J. Cheng, Y. Ke, S. Chu, and M. T. Ozsu. Efficient core decomposition in massive
networks. In ICDE. IEEE, 2011. [2] J. Cheng, L. Zhu, Y. Ke, and S. Chu. Fast algorithms for maximal clique enumeration with limited memory. In SIGKDD. ACM, 2012. [3] S. Chu and J. Cheng. Triangle listing in massive networks and its applications. In SIGKDD. ACM, 2011. [4] J. Cohen. Graph twiddling in a mapreduce world. Computing in Science & Engineering, 11(4):29–41, 2009. [5] J. D. Cohen. Trusses: Cohesive subgraphs for social network analysis. National Security Agency Technical Report, 2008. [6] J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI. USENIX Association, 2004. [7] W. Fan, X. Wang, and Y. Wu. Performance guarantees for distributed reachability queries. In VLDB. VLDB Endowment, 2012. [8] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI. USENIX Association, 2012. [9] J. Leskovec and C. Faloutsos. Scalable modeling of real graphs using kronecker multiplication. In ICML. ACM, 2007. [10] R.-H. Li, J. X. Yu, and R. Mao. Efficient core maintenance in large dynamic graphs. TKDE, 99(PrePrints):14, 2013. [11] Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed graphlab: a framework for machine learning and data mining in the cloud. In VLDB. VLDB Endowment, 2012. [12] G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD. ACM, 2010. [13] A. Montresor, F. De Pellegrini, and D. Miorandi. Distributed k-core decomposition. In SIGACT-SIGOPS. ACM, 2011. [14] A. E. Sarıyuce, B. Gedik, G. Jacques-Silva, K.-L. Wu, and U. V. Catalyurek. Streaming algorithms for k-core decomposition. In VLDB. VLDB Endowment, 2013. [15] S. Seo, E. J. Yoon, J. Kim, S. Jin, J.-S. Kim, and S. Maeng. Hama: An efficient matrix computation with the mapreduce framework. In CloudCom. IEEE, 2010. [16] J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural diversity in social contagion. In PNAS. National Acad Sciences, 2012. [17] L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103–111, 1990. [18] J. Wang and J. Cheng. Truss decomposition in massive networks. In VLDB. VLDB Endowment, 2012. [19] D.-N. Yang, Y.-L. Chen, W.-C. Lee, and M.-S. Chen. On social-temporal group query with acquaintance constraint. In VLDB. VLDB Endowment, 2011. [20] D.-N. Yang, C.-Y. Shen, W.-C. Lee, and M.-S. Chen. On socio-spatial group query for location-based social networks. In SIGKDD. ACM, 2012. [21] H. Yu, A. Paccanaro, V. Trifonov, and M. Gerstein. Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 22:823–829, 2006. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56335 | - |
dc.description.abstract | k-truss 是一種可以代表一個網路凝聚力大小的子圖,是在分析一個
社群網路的重要指標。然而,隨著巨量社群網路的出現,其構成的圖 會擁有百萬甚至上億個節點和邊,這導致k-truss 傳統單機版演算法所 需要的運算時間將會超乎想像的久;除此之外,如此大型的圖會無法 載入單一機器的記憶體,這也是另一個傳統演算法無法運作的原因。 目前,大資料的運算已經迫切的仰賴雲端運算,因此我們的目標是基 於雲端運算的框架上,設計出可以處理巨量資料的k-truss 演算法。在 本篇論文中,我們先就已經存在的MapReduce 版k-truss 演算法進行改 良。而由於MapReduce 的架構在處理分散式的圖運算時會因為太多的 迴圈而導致過多的IO 負載,我們轉而使用圖平行架構(graph-parallel anstractions) ,且提出一系列的理論基礎來設計一個k-truss 平行化演 算法的版本。實驗的結果顯示,從運算時間以及硬碟使用量的觀點來 看,我們基於圖平行架構所提出的k-truss 平行化演算法比其他基於 MapReduce 設計的版本來的更有效率。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T05:23:58Z (GMT). No. of bitstreams: 1 ntu-103-R01942069-1.pdf: 2775831 bytes, checksum: 8615e866645f3bbde4e822d3636891dc (MD5) Previous issue date: 2014 | en |
dc.description.tableofcontents | 口試委員會審定書i
誌謝ii 摘要iii Abstract iv 1 Introduction 1 2 Related Work 4 2.1 Graph-Parallel Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Social Measures in Large Graphs . . . . . . . . . . . . . . . . . . . . . . 5 3 Preliminaries 6 3.1 k-Truss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 k-Truss Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4 Distributed k-Truss Decomposition in MapReduce Framework 11 4.1 Basic Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Improved Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 Distributed k-Truss Decomposition based on Bulk Synchronous Parallel Model 17 5.1 Definition and Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 Algorithm in Graph Parallel Abstraction . . . . . . . . . . . . . . . . . . 21 5.3 Correctness and Convergence . . . . . . . . . . . . . . . . . . . . . . . . 25 5.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6 Experimental Analysis 30 6.1 Experiments on Synthetic Data . . . . . . . . . . . . . . . . . . . . . . . 30 6.2 Experiments on Real World Data . . . . . . . . . . . . . . . . . . . . . . 32 7 Conclusion 39 Bibliography 40 | |
dc.language.iso | en | |
dc.title | k-Truss 分解之分散式演算法 | zh_TW |
dc.title | Distributed Algorithms for k-Truss Decomposition | en |
dc.type | Thesis | |
dc.date.schoolyear | 102-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 呂俊賢,陳正君,楊得年,鄧維光 | |
dc.subject.keyword | k叢集,平行運算,社群網路,大數據, | zh_TW |
dc.subject.keyword | k-truss,parallel computing,social network,big data, | en |
dc.relation.page | 42 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2014-08-15 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
顯示於系所單位: | 電信工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 2.71 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。