문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 시스템 벤치마크]] == 개요 == https://github.com/sbeamer/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이 얼마나 있는지 계산한다. == 사용한 알고리즘 == * Breadth-First Search (BFS) - direction * Single-Source Shortest Paths (SSSP) - delta stepping * PageRank (PR) - iterative method in pull direction * Connected Components (CC) - Afforest & Shiloach-Vishkin * Betweenness Centrality (BC) - Brandes * Triangle Counting (TC) - Order invariant with possible relabelling Gapbs 문서로 돌아갑니다.