Pairwise trust inference by subgraph extraction

Yuan Yao, Hanghang Tong, Feng Xu, Jian Lu

Research output: Contribution to journalArticlepeer-review


Inferring pairwise trustworthiness is a core building block behind many real applications, e.g., e-commence, 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 top-k 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 method.

Original languageEnglish (US)
Pages (from-to)953-968
Number of pages16
JournalSocial Network Analysis and Mining
Issue number4
StatePublished - Jan 1 2013
Externally publishedYes


  • Component induction
  • Pairwise trustworthiness
  • Path selection
  • Social network
  • Subgraph extraction
  • Trust inference

ASJC Scopus subject areas

  • Information Systems
  • Communication
  • Media Technology
  • Human-Computer Interaction
  • Computer Science Applications


Dive into the research topics of 'Pairwise trust inference by subgraph extraction'. Together they form a unique fingerprint.

Cite this