Fast and Accurate Trust Computation in Online Social Networks

Abstract

In online social networks (OSNs) trust plays an important role in user activities. It can allow users to distinguish between reliable and malicious users and the content produced by them. Evaluating trust between users of OSNs that are not directly connected is an important research problem. Moreover, considering the large size of these OSNs, it’s important that the trust computation methods should be fast. To address this issue, we work on two aspects of trust computation in OSNs, efficiency and accuracy. For the efficiency aspect we make an existing trust computation method fast enough to be applied on very large networks. For the accuracy aspect we propose a trust/distrust computation method that is more accurate than existing methods and is also fast enough to be applied on very large networks. In addition, this method is also robust to missing edges. In the first part dealing with efficiency, we make the already proposed min-max trust computation strategy fast enough to be applied on very large networks. For this we use the landmark based method that has been used in fast graph searching algorithms. Strength of trust path between every node and a small set of reference or landmark nodes is pre-computed. Using these pre-computed values, we estimate the strength of paths from the source user to in-neighbors of the target user. The final trust estimate is obtained by aggregating information from most reliable in-neighbors of the target user. Experiments on a variety of real-world social network datasets verify the efficiency and accuracy of our method. In the second part we provide a fast and accurate method for estimating level of trust or distrust from trustor to trustee. Our method is based on co-citation and transpose trust propagation. We determine on average how differently two users trust or are trusted by common users, and how differently a user trusts another user from how it is trusted by that user. Using these differences, we estimate four partial trust estimates and compute the final trust value from trustor to trustee as the weighted average of these partial estimates. We propose a basic framework that maximizes accuracy, robustness and coverage and then show how we can further improve the accuracy at a lower coverage. We perform experiments on trust related datasets which show that our proposed method out-performs some of the state-of-the-art trust computation methods in terms of accuracy and robustness.; 온라인 소셜 네트워크에서 신뢰성은 사용자 활동에서 중요한 역할을 한다. 사용자가 생산한 콘텐츠 또는 사용자 자신에 대해 믿을만한 지 혹은 악의적인 의도인지를 구별할 수 있도록 해주기 때문이다. 직접적 연결 관계가 없는 사용자들 사이에서 신뢰성을 계산하는 것은 중요한 연구 과제가 되어 왔다. 또한 온라인 소셜 네트워크의 방대한 크기를 생각해 볼 때, 그것에 대한 계산은 계산이 신속하게 수행되는 것이 매우 중요하다. 이런 주제로 본 논문에서는 효율성과 정확성이라는 두가지 측면에서 온라인 소셜 네트워크 상에서 신뢰성 계산 방법에 대해 연구하였다. 효율성 측면에서 우리는 기존의 신뢰성 계산 방법을 매우 큰 온라인 네트워크 상에서도 사용할 수 있도록 만들었다. 정확성 측면에서 우리는 신뢰성과 불신뢰성 병행 계산 방법을 제안함으로써 기존의 방법보다 훨씬 더 빠르게 대용량 네트워크에서 신속하고 정확한 산정이 가능하도록 하였다. 본 논문에서 제안한 이 방법은 네트워크 상에 끊어진 연결 고리가 있는 경우에도 여전히 강건하게 작동한다.

효율성 목표를 달성하기 위해 우리는 기존의 최대-최소 신뢰성 계산 전략을 대용량 온라인 네트워크에 적용가능하도록 만들었다. 이를 위해 우리는 매우 빠른 그래프 검색 알고리즘에서 흔히 사용되는 랜드마크 기반 방법을 사용한다. 그래프상 노드와 특정 참조 집단 또는 랜드마크 노드간의 신뢰성의 강도는 미리 계산해 놓을 수 있다. 이렇게 미리 계산된 값들을 이용해서 우리는 시작노드에서 목표 노드의 in-neighbors 노드까지 경로의 강도를 산정할 수 있다. 최종 신뢰성 값은 목표 노드의 in-neighbors 노드 중에서 가장 신뢰성 높은 값들을 합산하는 방식으로 계산한다. 신뢰받는 사람과 신뢰하려는 사람간의 신뢰성/불신뢰성 정보를 신속하면서도 정확성을 유지하는 방법이다. 우리의 방법은 신뢰성 전파상의 동시인용(co-citation)과 교체배치(transpose) 방법에 기반한 해결책이다. 이 방법은 평균적으로 두 사용자간의 신뢰성 또는 다른 공통적인 사용자로부터 두 사용자가 어떻게 다르게 신뢰성을 나타내는지를 결정할 수 있다. 또한 어떤 사용자가 다른 사용자들로부터 어떻게 다르게 신뢰받고 있는지도 결정할 수 있다. 이런 차이를 이용하여 우리는 네가지 서로 다른 부분 신뢰 산정값을 계산하며, 이러한 부분 산정값들의 가중평균값을 구하는 방법으로 신뢰받는 사람과 신뢰하려는 사람값의 최종값을 빠르고 정확하게 계산한다. 우리는 정확성(accuracy), 강건성(robustness), 그리고 적용범위(coverage)를 극대화하는 기본 프레임워크를 제안하며 적용범위가 좁아졌을 때 정확성을 좀더 개선할 수 있도록 하였다. 이러한 점에 대해서는 관련 데이터세트를 대상으로 유효성을 판단할 수 있는 충분한 실험을 수행하였으며 본 학위논문에서 제시한 방법은 다른 최신의 신뢰성 계산 방법보다 정확성이나 강건성 측면에서 볼 때 대단히 우월한 결과를 나타냄을 입증하였다.