> 뉴스 > 대학뉴스 > 학술,연구 | 실시간 교육/대학뉴스
     
서울대, 랜덤 워크 기반 고속 랭킹 기법 개발
강유 교수 연구팀, 실세계 그래프의 구조적 특징 활용
2016년 12월 20일 (화) 15:19:04
   
▲강유 교수 

[대학저널 이원지 기자]서울대학교(총장 성낙인) 컴퓨터공학부 강 유 교수 연구진은 소셜 네트워크, 웹, 그래프 기반 추천 시스템 등의 랭킹에 널리 활용되는 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/)


이원지 기자 wonji@dhnews.co.kr
ⓒ 대학저널(http://www.dhnews.co.kr/) 무단전재 및 재배포금지 | 저작권문의  

     
회사소개 인터넷신문위원회 자율규약 준수 광고 제휴문의 개인정보취급방침 청소년보호정책 이메일 무단수집 거부
(주)대학저널 | [주소] 08511 서울특별시 금천구 디지털로 9길65, 906호(가산동 백상스타타워1차) | TEL 02-733-1750 | FAX 02-754-1700
발행인 · 대표이사 우재철 | 편집인 우재철 | 등록번호 서울아01091 | 등록일자 2010년 1월 8일 | 제호 e대학저널 | 청소년보호책임자 우재철
Copyright 2009 대학저널. All rights reserved. mail to press@dhnews.co.kr