Gapbs

개요

그래프 알고리즘은 점점 여러 분야에 사용되면서 중요성을 보이고 있다. 이러한 그래프 알고리즘의 처리에 대한 standard한 벤치마크를 제공하기 위해서 Graph500과 같은 유수의 그래프 탐색 경진대회에서 사용한 알고리즘을 이용한 벤치마크이다.

모두 6가지의 그래프들이 사용되었으며, 각각의 그래프는 social network, engineering, science 와 같은 분야에서 주로 나타나는 패턴을 대표할 수 있도록 하였다.

Breadth-First Search (BFS): BFS는 그래프를 depth를 1씩 증가시키면서 현재 depth에 해당하는 모든 노드를 검사한다.
Single-Source Shortest Paths (SSSP): 특정한 source node에서 다른 모든 노드로 향하는 최단 거리를 계산하였다. 모든 grpah weight은 양의 값으로 가정하여 구하였다.
PageRank (PR): 그래프의 모든 정점에 대한 PageRank를 계산하였다. PageRank는 검색엔진에서 주로 쓰이는 노드의 중요도를 계산하는 알고리즘이다.
Connected Componenets (CC): Graph에서 서로 연결된 그래프들의 개수를 구하고 각각의 Connected Componenet에 대해서, 라벨을 할당한다. https://en.wikipedia.org/wiki/Component_(graph_theory)
Betwenness Centrality (BC): 그래프에서, 한 노드가 얼마나 중요한 의미를 가지고 있는지 계산한다. 이때 BC를 계산할때 중요도는, Shortest path에서 그 정점을 얼마나 많은 노드들이 건너냐로 계산할 수 있다.
Triangle Counting (TC): 그래프에서 노드 3개가 연결된 triangle이 얼마나 있는지 계산한다.