동적 그래프에서 PageRank를 업데이트하는 증분 방법의 비교 분석

링크 표

초록 및 서론 1편

2 관련 업무

3 예선

4 접근

5.1 실험 설정

5.2 Dynamic Frontier PageRank의 성능

5.3 동적 프론티어 PageRan의 강력한 확장

6 결론, 감사의 말씀, 참고문헌

대략적인 PageRank의 증분 계산(동적/진화 그래프에서 PageRank 값 업데이트)을 수행하기 위한 다양한 접근 방식이 제안되었습니다. Chien et al. [6] 업데이트된 정점 근처의 그래프의 작은 영역을 식별하고 그래프의 나머지 부분을 훨씬 더 작은 새 그래프의 단일 정점으로 모델링합니다. PageRank는 작은 그래프에 대해 계산된 다음 원본 그래프로 전송됩니다. Chenet al. [5] 역방향 하이퍼링크를 따라 대상 노드에서 뒤로 확장하여 전체 웹의 작은 하위 그래프만을 사용하여 특정 웹 페이지의 PageRank 점수를 추정하는 다양한 방법을 제안합니다. Bahmaniet al. [2] PageRank의 증분 계산을 위한 Monte Carlo 방법의 효율성을 분석합니다. Zhanet al. [24] 각 노드에서 시작하는 𝑅 무작위 이동을 유지하여 동적 네트워크에서 PageRank 추적을 위한 Monte Carlo 기반 알고리즘을 제안합니다. Pashikantiet al. [20] 또한 정점 및 가장자리 삽입/삭제에 대한 PageRank 점수를 업데이트하기 위해 유사한 접근 방식을 따릅니다.

동적 그래프에서 정확한 PageRank 점수를 업데이트하기 위한 몇 가지 접근 방식이 제안되었습니다. 장 [25] UGAS(Update-GatherApply-Scatter) 계산 모델을 통합하는 하이브리드 CPU 및 GPU 플랫폼의 동적 그래프를 위한 간단한 증분 Pagerank 계산 시스템을 제시합니다. 입력 그래프에 작은 변화가 있는 경우 동적 PageRank 알고리즘에 사용되는 일반적인 접근 방식은 전처리 단계에서 BFS(Breadth-First Search) 또는 DFS(Depth-First Search) 탐색을 통해 영향을 받는 영역을 찾는 것입니다. 삽입되거나 삭제된 가장자리 및 해당 영역에 대해서만 PageRank를 계산합니다. [7, 12, 13, 22]. 이 접근법은 원래 Desikan et al.에 의해 제안되었습니다. [7]. 김과 최 [13] PageRank의 비동기 구현과 함께 이 접근 방식을 사용하세요. Giriet al. [12] 다중 코어 CPU 및 대규모 병렬 GPU에서 공동 실행에 이 접근 방식을 사용합니다. Sahuet al. [22] SCC(Strongly Connected Component) 기반 그래프 분해에 이 접근 방식을 사용하여 멀티 코어 CPU 및 GPU(별도)의 업데이트된 정점에서 도달할 수 있는 SCC로 계산을 제한합니다. Ohsakaet al. [18] 가장 큰 잔차를 가진 정점이 먼저 업데이트되는 Gauss-Southwell 방법을 사용하여 PageRank를 로컬로 업데이트하는 접근 방식을 제안합니다. 그러나 해당 알고리즘은 본질적으로 순차적입니다.

또한, Bahmani et al. [3] Berberich et al.은 그 순간 그래프의 실제 PageRank 추정치를 제공하기 위해 웹의 작은 부분을 선택적으로 크롤링하는 알고리즘을 제안합니다. [4] 그래프의 비국소적 변화에 강력한 정규화된 PageRank 점수를 계산하는 방법을 제시합니다. 이들의 접근 방식은 웹 크롤링이나 표준화된 점수 유지 프로세스가 아닌 PageRank 벡터 자체의 계산에 초점을 맞춘 Dynamic Frontier 접근 방식과 직교합니다.