BIRD: 양방향 숨겨진 개인화 페이지랭크의 효율적인 근사

이분 그래프 분석에서 유사도 측정은 다양한 응용 프로그램에서 중요한 역할을 합니다. 기존 메트릭 중 양방향 숨겨진 개인화 페이지랭크(BHPP)는 우수한 질의 품질로 두각을 나타냅니다. 그러나 BHPP의 계산 비용은 여전히 병목 현상입니다. 기존 근사 방법은 상당한 행렬 저장 공간을 요구하거나 천문학적인 시간 비용을 초래합니다. 예를 들어, 현재의 최신 방법은 약 3 × 10 8개의 엣지를 포함하는 실제 이분 그래프 Orkut에서 단일 소스 BHPP 쿼리를 처리하는 데 3시간 이상 걸립니다. 우리는 가중치가 있는 이분 그래프에서 단일 소스 BHPP 쿼리를 답하기 위해 설계된 새로운 알고리즘 BIRD를 소개합니다. 철저한 이론 분석을 통해 우리는 BIRD가 전형적인 상대 오차 설정 및 일정한 실패 확률 하에서 이전 최적 방법 Õ (m)에 비해 시간 복잡도를 Õ(n)으로 크게 개선함을 입증합니다. (n, m은 각각 노드와 엣지의 수를 나타냅니다.) 광범위한 실험 결과 BIRD가 대규모 이분 그래프에서 기존 기준보다 여러 배 성능을 발휘함을 확인했습니다. 특히, 우리가 제안한 방법은 Orkut에서 단일 소스 BHPP 쿼리를 단 7분 만에 완료합니다.