BFS에 기반한 포스트 랭킹: 알고리즘 및 성능 평가

Abstract

기존의 포스트 랭킹 알고리즘에서 포스트의 랭킹은 해당 포스트와 연관된 블로거의 능력이나 연관된 포스트들의 품질에 의하여 결정된다. 크게 연관성이 없는 포스트나 블로거도 포스트의 랭킹에 영향을 미칠 수 있으며, 정확도를 떨어뜨리는 요인으로 작용할 수 있다. 본 논문에서는 이러한 문제점을 해결하기 위하여 BFS에 기반한 포스트 랭킹 알고리즘인 PBFS를 제안한다. PBFS는 특정 포스트의 랭킹을 계산하기 위하여 그와 연관된 블로거와 포스트를 제한하고, 연관성에 따른 가중치를 부여하여 정확도를 향상한다. PBFS의 정확도를 검증하기 위하여 실제 데이터를 이용한 실험을 수행하였으며, 제안하는 PBFS가 기존 포스트 랭킹 알고리즘보다 우수한 정확도를 보였다. Existing post ranking algorithms assume that the ranking of a post is related to both of the relevant posts and bloggers connected by blog-actions such as trackbacks, scraps, and comments. For this reason, existing algorithms factor in distant related posts/bloggers, which negatively influences ranking accuracy. In this paper, to eliminate the effect of less related posts and bloggers in ranking, we propose a novel post ranking algorithm, PBFS. This algorithm selects the relevant posts and bloggers in the manner of the breadth first search and additionally considers weights by the relatedness between a target post and the other posts/bloggers. We evaluate the accuracy of ranking algorithms by performing extensive experiments using real-world blog data. The experimental results reveal that our algorithm outperforms the existing algorithms.