Pairwise trust inference by subgraph extraction

Authors: Yuan Yao Hanghang Tong Feng Xu Jian Lu

Publish Date: 2013/10/06

Volume: 3, Issue: 4, Pages: 953-968

PDF Link

Abstract

Inferring pairwise trustworthiness is a core building block behind many real applications eg ecommence p2p networks mobile ad hoc network etc Most of the existing inference algorithms suffer from the scalability and usability issues due to the large scale of the underlying social networks In this paper we propose subgraph extraction to address these challenges The core of the proposed method consists of two stages path selection and component induction The path selection stage is flexible and it admits many of existing topk path extraction algorithms We propose two evolutionary algorithms for component induction stage Our method has two main advantages First the outputs of both stages can be used as an intermediate step to speed up a variety of existing trust inference algorithms Second it improves the usability of the trust inference result by presenting an intuitive subgraph that concisely summarizes how the trustworthiness score is calculated The extensive experimental evaluations on real datasets demonstrate the effectiveness and efficiency of the proposed methodWe would like to thank Chao Qian for his useful comments This work is supported by the National Natural Science Foundation of China Nos 61021062 61073030 and the National 973 Program of China No 2009CB320702 The second author was partly sponsored by the Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF0920053

Keywords: