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.
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.
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