서울대학교 컴퓨터공학부 강 유 교수 연구진은 소셜 네트워크, 웹, 그래프 기반 추천 시스템 등의 랭킹에 널리 활용되는 RWR (Random Walk with Restart) 알고리즘이 대용량 그래프를 빠르게 처리하지 못하는 문제를 해결하였다.
RWR은 그래프에서 랜덤 워크 (Random Walk)를 통해 한 정점을 기준으로 다른 정점에 대한 중요도를 계산하는 랭킹 기법으로 개인화된 추천에 적합하여 정점 랭킹, 추천 시스템, 링크 예측 등의 다양한 그래프 마이닝 응용에 활발하게 활용되고 있다. 예를 들어 소셜 네트워크에서 특정 사용자와 다른 모든 사용자간의 유사도를 계산하여 유사도가 높지만 아직 연결이 안 된 사용자들을 찾음으로써 그 사용자에게 새로운 친구를 추천하는데 쓰이고 있다.
기존의 RWR을 계산하는 알고리즘은 반복적 기법과 전처리 기법으로 분류되는데 반복적 기법은 메모리를 적게 사용하여 대규모 그래프를 처리할 수는 있으나, RWR의 계산 속도가 느리다는 단점이 있다. RWR 계산 속도를 빠르게 하기 위해 여러 전처리 기법이 제안되었지만 전처리 기법은 메모리를 과도하게 사용하기 때문에 대용량 그래프를 처리하지 못한다.
강 유 교수 연구진은 실세계 그래프의 구조적 특징을 이용하고 반복적 기법과 전처리 기법의 조합으로 기존 방법들의 장점을 취해 대용량 그래프에서 빠르고 메모리 효율적인 RWR 알고리즘을 개발하였다. 논문에서 제안한 알고리즘은 기존 알고리즘보다 100배 이상 큰 그래프를 처리할 수 있고 130배 이상 메모리를 적게 사용하면서 실행 시간은 9배 빠르되, 같은 정확도를 제공하도록 설계되었다.
본 연구결과를 통해 RWR을 기반으로 하는 응용의 계산 확장성과 속도를 크게 향상시킬 수 있기 때문에 그래프를 바탕으로 RWR을 활용하는 그래프 마이닝, 정보 검색, 인공지능, 생물정보학 등 다양한 분야에 도움이 될 것으로 기대한다.
본 연구는 서울대학교 컴퓨터공학부 강유 교수 연구진이 주도하였으며 한국뉴욕주립대 이 슬 교수도 참여했다.
이번 연구 결과는 데이터베이스와 빅데이터 분야에서 세계 최고 학회인 ACM SIGMOD 2017 (ACM International Conference on Management of Data)에 채택되어 2017년 5월 중순 미국에서 발표될 예정이다. (http://sigmod2017.org/)