상단여백
HOME 대입 대학뉴스
서울대, 대용량 그래프에서 랜덤 워크 기반 고속 랭킹 기법 개발실세계 그래프의 구조적 특징을 활용
  • 김경화 기자
  • 승인 2016.12.20 13:52
  • 호수 0
  • 댓글 0

[베리타스알파=김경화 기자] 서울대는 컴퓨터공학부 강유 교수 연구진이 소셜 네트워크, 웹, 그래프 기반 추천 시스템 등의 랭킹에 널리 활용되는 RWR 알고리즘이 대용량 그래프를 빠르게 처리하지 못하는 문제를 해결했다고 20일 밝혔다.   

RWR(Random Walk with Restart)은 그래프에서 랜덤 워크(Random Walk)를 통해 한 정점을 기준으로 다른 정점에 대한 중요도를 계산하는 랭킹 기법으로 개인화된 추천에 적합하여 정점 랭킹, 추천 시스템, 링크 예측 등의 다양한 그래프 마이닝 응용에 활발하게 활용되고 있다. 예를 들어 소셜 네트워크에서 특정 사용자와 다른 모든 사용자간의 유사도를 계산하여 유사도가 높지만 아직 연결이 안 된 사용자들을 찾음으로써 그 사용자에게 새로운 친구를 추천하는데 쓰이고 있다.

기존의 RWR을 계산하는 알고리즘은 반복적 기법과 전처리 기법으로 분류되는데 반복적 기법은 메모리를 적게 사용하여 대규모 그래프를 처리할 수는 있으나, RWR의 계산 속도가 느리다는 단점이 있다. RWR 계산 속도를 빠르게 하기 위해 여러 전처리 기법이 제안되었지만 전처리 기법은 메모리를 과도하게 사용하기 때문에 대용량 그래프를 처리하지 못한다.

서울대 강유 교수 연구진은 실세계 그래프의 구조적 특징을 이용하고 반복적 기법과 전처리 기법의 조합으로 기존 방법들의 장점을 취해 대용량 그래프에서 빠르고 메모리 효율적인 RWR 알고리즘을 개발하였다. 논문에서 제안한 알고리즘은 기존 알고리즘보다 100배 이상 큰 그래프를 처리할 수 있고 130배 이상 메모리를 적게 사용하면서 실행 시간은 9배 빠르되, 같은 정확도를 제공하도록 설계되었다.

연구결과를 통해 RWR을 기반으로 하는 응용의 계산 확장성과 속도를 크게 향상시킬 수 있기 때문에 그래프를 바탕으로 RWR을 활용하는 그래프 마이닝, 정보 검색, 인공지능, 생물정보학 등 다양한 분야에 도움이 될 것으로 기대한다. 

연구는 서울대 컴퓨터공학부 강유 교수 연구진이 주도하였으며 한국뉴욕주립대 이 슬 교수도 참여했다. 연구 결과는 데이터베이스와 빅데이터 분야에서 세계 최고 학회인 ACM SIGMOD 2017에 채택되어 내년 5월 중순 미국에서 발표될 예정이다.

 
본 기사는 교육신문 베리타스알파의 고유 콘텐츠입니다.
일부 게재 시 출처를 밝히거나 링크를 달아주시고 사진 도표 기사전문 게재 시 본사와 협의 바랍니다.
여백

김경화 기자  smile@veritas-a.com

<저작권자 © 베리타스알파, 무단 전재 및 재배포 금지>

김경화 기자의 다른기사 보기
icon인기기사
기사 댓글 0
전체보기
첫번째 댓글을 남겨주세요.
Back to Top