부호형 그래프 요약 기법

Abstract

소셜 네트워크 서비스, 전자 상거래 등 다양한 웹 서비스들의 사용량이 폭발적으로 증가하고 있으며, 해당 정보들을 표현하기 위한 그래프의 규모 역시 기하급수적으로 증가하고 있다. 이러한 대용량 그래프를 효율적으로 활용하기 위해 정보손실을 최소화하면서 간결한 요약 그래프를 얻어내는 그래프 요약 방법이 제안되었다. 하지만 기존 그래프 요약 방법은 기본 또는 가중 그래프만을 대상으로 연구되어, 긍정 및 부정적 관계를 포함하고 있는 부호형 그래프를 다루고 있지 않다. 부호형 그래프는 소셜 미디어, 전자 상거래뿐만 아니라 국방 분야의 다양한 군 관련 정보들에서 흔히 나타나는 긍정 및 부정적 관계들을 포함한 그래프이다. 본 논문에서는 부호형 그래프의 간선과 간선의 부호까지 잘 유지하는 비용함수를 사용하여 정보손실을 최소화하는 새로운 그래프 요약 기법을 제안하였다. 또한, 제안 방법이 기존 방법 대비 최대 24.83% 오차가 적었고, 부호형 그래프의 구조적 균형 또한 잘 유지함을 실험적으로 보였다.