Efficient counting of triangles in a very large graph with mapreduce = 대용량 그래프에서 삼각형의 수를 계산하는 맵리듀스 알고리즘

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 369
  • Download : 0
Triangle counting problem is one of the fundamental problem in various domains. The problem can be utilized for computation of clustering coefficient, transitivity, trianglular connectivity, trusses, etc. The problem have been extensively studied in internal memory but the algorithms are not scalable for enormous graphs. In recent years, the MapReduce has emerged as a de facto standard framework for processing large data through parallel computing. A MapReduce algorithm was proposed for the problem based on graph partitioning. However, the algorithm redundantly generates a large number of intermediate data that cause network overload and prolong the processing time. In my thesis, I propose a new algorithm based on graph partitioning with a novel idea of triangle classification to count the number of triangles in a graph. The algorithm substantially reduces the duplication by classifying triangles into three types and processing each triangle differently according to its type. In the experiments, I compare the proposed algorithm with recent existing algorithms using both synthetic datasets and real-world datasets that are composed of milions of nodes and billions of edges. The proposed algorithm outperforms other algorithms in most cases. Especially, for a twitter dataset, the proposed algorithm is more than twice as fast as existing MapReduce algorithms. Moreover, the performance gap increases as the graph becomes larger and denser.
Advisors
Chung, Chin-Wanresearcher정진완
Description
한국과학기술원 : 웹사이언스공학전공,
Publisher
한국과학기술원
Issue Date
2013
Identifier
566503/325007  / 020114372
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 웹사이언스공학전공, 2013.8, [ iv, 27 p. ]

Keywords

triangle; mapreduce; 그래프; 삼각형; graph; 맵리듀스

URI
http://hdl.handle.net/10203/197097
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=566503&flag=dissertation
Appears in Collection
WST-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0