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.
그래프에서 삼각형의 수를 세는 문제는 다양한 분야에서 기본적인 문제 중 하나이다. 이 문제는 그래프 분석 분야에서 중요한 척도인 집단화 계수(clustering coefficient)와 이행률(transitive ratio)을 계산하는데 필수적이다. 내장형 메모리 환경에서 동작하는 다양한 알고리즘들이 제안되었으나 이러한 알고리즘들은 대규모 그래프를 처리하기 힘들다. 최근, 맵리듀스는 분산 컴퓨팅을 통하여 대용량 데이터를 처리하는 사실상의 표준으로 등장했다. 이러한 흐름에 따라, 그래프에서 삼각형의 수를 세기 위한 맵리듀스 알고리즘이 최근에 제안되었다. 하지만 이 알고리즘은 삼각형을 계산하는 과정에서 많은 중간 산출물을 배출하여 네트워크 부하를 일으키고 수행시간을 지연시킨다. 본 논문에서는 그래프 파티셔닝 기법(graph partitioning)에 기반한 새로운 알고리즘을 제안한다. 이 알고리즘은 그래프가 나뉘어졌을 때 삼각형을 세 가지 유형으로 분류하고, 각 유형마다 다르게 처리하여 기존 알고리즘의 성능을 향상시켰다. 그리고 실세계 데이터와 인조 데이터를 이용한 실험을 통해서 제안하는 알고리즘과 기존의 알고리즘을 비교하였다. 제안하는 알고리즘이 대부분의 경우에 기존의 알고리즘들보다 빠른 성능을 보였다. 특히, 트위터 데이터를 이용한 실험에서, 제안하는 알고리즘이 기존의 알고리즘보다 두 배 이상 빠른 성능을 보였다. 더욱이 그래프가 커지고 조밀해질 수록 알고리즘간의 성능 차이가 커졌다.
