Discovery of the Optimal Trust Inference Path for Online Social Networks

Yao Ma, Hongwei Lu, Zaobin GanIEICE 2014 · DOI

Abstract

Analysis of the trust network proves beneficial to the users in Online Social Networks (OSNs) for decision-making. Since the construction of trust propagation paths connecting unfamiliar users is the preceding work of trust inference, it is vital to find appropriate trust propagation paths. Most existing trust network discovery algorithms apply classical exhausted searching approaches with low efficiency and/or disregard the role of distrust relationships. To solve these issues, we first analyze trust discounting operators with structural balance theory and validate the distribution characteristics of balanced transitive triads. Then, Maximum Indirect Referral Belief Search (MIRBS) and Minimum Indirect Functional Uncertainty Search (MIFUS) strategies are proposed, followed by the Optimal Trust Inference Path Search (OTIPS) algorithms based on bidirectional versions of Dijkstra's algorithm. Experimental results on the Epinions dataset show that the proposed algorithm finds trust inference paths with better efficiency and applicability.

Introduction

In Online Social Networks (OSNs) like Epinions or LinkedIn, users often need to evaluate the trustworthiness of people they do not know personally. This process, known as trust inference, relies on finding a path of recommendations through intermediaries. For example, if Alice trusts Bob, and Bob trusts Charlie, Alice can infer a level of trust for Charlie. However, finding the "best" path in a massive network presents two major hurdles: high computational complexity and the historical neglect of distrust relationships.

Methodology

The authors propose two new search strategies based on Subjective Logic, which represents opinions as a combination of belief, disbelief, and uncertainty.

  • MIRBS (Maximum Indirect Referral Belief Search): This strategy seeks the path providing the highest possible "referral belief" from intermediaries.
  • MIFUS (Minimum Indirect Functional Uncertainty Search): This strategy focuses on finding the path that results in the least amount of uncertainty regarding the target user.
A complex trust network illustrating potential propagation paths between a source participant and a target participant.

To implement these strategies at scale, the OTIPS algorithm was developed. Unlike standard one-way searches, OTIPS is a bidirectional version of Dijkstra’s algorithm, searching from both the source and the target simultaneously to meet in the middle. This approach drastically reduces the number of nodes the system must evaluate during the search process.

Structural Balance Theory

Crucially, the researchers integrate Structural Balance Theory to handle negative relationships (distrust). This allows the algorithm to navigate "balanced triads"—for instance, applying the social logic that "the enemy of my enemy is my friend." By incorporating distrust as an informative signal rather than just an obstacle, the model can deduce trust even through complex paths containing negative edges.

Undirected signed triads used to model structural balance and the role of distrust in social networks.

Experimental Results

The researchers evaluated their model using the Epinions dataset, consisting of approximately 132,000 users and over 840,000 trust/distrust statements. The OTIPS algorithm significantly outperformed established benchmarks like TidalTrust and CertProp:

  • Efficiency: OTIPS (MIRBS) and OTIPS (MIFUS) scanned 67.5% and 58.4% fewer vertices than TidalTrust, respectively.
  • Coverage: The proposed algorithms found valid trust paths for 7.6% more users than TidalTrust.
  • Accuracy: The "Belief Error" (B-error) was reduced by 7.4% to 8.9% compared to existing methods.
  • Edge Prediction: The system achieved an accuracy (ACC) of approximately 70-71% in predicting whether a relationship was positive or negative.

Conclusion

The OTIPS algorithm demonstrates that "global optimality" in trust path searching is computationally feasible through bidirectional search and the application of structural balance theory. By treating distrust as a valuable signal and focusing on minimizing uncertainty, the system provides more reliable trust inferences. Future work will extend the algorithm to find and fuse multiple optimal paths to further increase robustness.

Summary updated

Abstract

Analysis of the trust network proves beneficial to the users in Online Social Networks (OSNs) for decision-making. Since the construction of trust propagation paths connecting unfamiliar users is the preceding work of trust inference, it is vital to find appropriate trust propagation paths. Most of existing trust network discovery algorithms apply the classical exhausted searching approaches with low efficiency and/or just take into account the factors relating to trust without regard to the role of distrust relationships. To solve the issues, we first analyze the trust discounting operators with structure balance theory and validate the distribution characteristics of balanced transitive triads. Then, Maximum Indirect Referral Belief Search (MIRBS) and Minimum Indirect Functional Uncertainty Search (MIFUS) strategies are proposed and followed by the Optimal Trust Inference Path Search (OTIPS) algorithms accordingly on the basis of the bidirectional versions of Dijkstra's algorithm. The comparative experiments of path search, trust inference and edge sign prediction are performed on the Epinions data set. The experimental results show that the proposed algorithm can find the trust inference path with better efficiency and the found paths have better applicability to trust inference.
BibTeX
@inproceedings{ma2014discovery,
  author = {Yao Ma and Hongwei Lu and Zaobin Gan},
  title = {{Discovery of the Optimal Trust Inference Path for Online Social Networks}},
  booktitle = {IEICE},
  year = {2014},
  doi = {10.1587/transinf.e97.d.673},
}
Figure