2019.03.18 산업체 특강

 

분산 시스템을 이용하여 대규모 그래프에 존재하는 모든 삼각형 찾아내기

 

국민대학교 박하명 교수님

 

문제 정의 :

 

Given undirected simple graph G=(V, E)

Enumerate all triangles in G

 

 

분산 시스템이란?

인터넷에 연결된 여러 컴퓨터들의 처리 능력을 이용하여 거대한 계산 문제를 해결하려는 분산처리 모델이다.

하둡이나 스파크 등이 있다.

 

삼각형 : 3개의 노드가 모두 연결되어있는 것

 

왜 그래프에서 삼각형을 찾을까?

 

그래프는 아래 예시와 같이 다양하게 많이 사용 한다. 

-freindship network

-phonecall network

-knowledge base

 

-인터넷 www (페이지 링크)

 

-> 여러 그래프 관계에서 삼각형 구조를 이루고 있기 때문에 그래프에서 삼각형을 찾는다!

 

 

분산환경 시스템에서 HDFS(Hadoop File System)을 사용한다. 네트워크가 High-speed Network 이기 때문에 이를 통해

다른 서버에 있는 데이터를 불러들여 사용한다. 이를 분산 시스템 환경으로 만들고 파일의 관리를 이 시스템에 맡긴다.

거대한 그래프는 분산 시스템에 저장되고 각각의 머신에서 필요한 edge와 node를 불러오고 subgraph에서 삼각형을

모두 찾은 후, 그 결과를 다시 분산 파일 시스템에 저장하게 된다.

 

Intersection of 2 neighbor sets -> Triangle

간단한 삼각형 찾는 알고리즘을 적용한다. 정점(node)들을 색칠하고 몇 개의 subproblem으로 나누어서 해결할 수 있다.

첫번째 subproblem은 빨,파,초록으로 이루어진 모든 삼각형을

두번째 subproblem은 빨,초,노랑으로 이루엊니 모든 삼각형을 찾는 식으로

분산 시스템을 사용해서 그래프의 전체 삼각형을 구할 수 있다.