큰 그래프에서의 모든 쌍에 대한 빠른 2 단계 랜덤 워크 계산 방법

Abstract (Korean)

현재 이종 그래프에 대한 연구가 활발히 진행되고 있다. 특히 추천 및 검색 분야에서 이종 그래프를 활용하여 성능을 높이는 성과가 두드러진다. 이종 그래프는 다양한 정보를 갖고 있으며, 특히 2단계 랜덤 워크 확률은 여러 유용한 정보를 가지고 있다. “어떤 사용자가 많이 본 영화를 많이 본 사용자”, “어떤 사용자의 이웃이 많이 구입한 상품” 등이 그예이다. 하지만 이러한 정보를 실시간에 계산하기는 어려우며, 미리 계산해두는 것도 시간이 많이 든다. 이에 따라, 본 연구에서는 모든 출발 노드-도착 노드 쌍에 대한 2단계 랜덤 워크를 빠르게 미리 계산하는 알고리듬을 제시한다. 동일한 이웃 노드를 다수 가진 두 노드에서 출발하는 랜덤 워크 확률 값은 서로 비슷하다는 사실을 이용하여, 이전 계산 결과를 활용하여 근접 노드 목록에 대한 임의 접근 횟수를 줄인다. 더불어 본 알고리듬과 관련된 현안을 몇 가지 소개한다.