Optimal Social Trust Path Selection in Complex Social Networks

Guanfeng Liu, Yan Wang, Mehmet A. Orgun

Introduction

In the vast landscape of modern social networks, establishing trust between distant participants is a fundamental challenge. When a source participant, such as an employer, needs to evaluate a target participant with whom they have no direct connection, they must rely on a chain of intermediaries. This process, known as trust propagation, is complicated by the "small-world" nature of these networks, where thousands of potential paths may exist between any two individuals.

Existing systems often simplify this by seeking the shortest path or the highest raw trust score. However, these metrics often ignore critical real-world factors like social intimacy and professional expertise. Finding an optimal path that balances these multiple constraints is a Multi-Constrained Optimal Path (MCOP) problem, which is NP-Complete and computationally expensive in large-scale networks.

The Quality of Trust (QoT) Model

To address these complexities, the authors propose a Quality of Trust (QoT) metric, drawing parallels to Quality of Service (QoS) in networking. Every link in a potential trust path is characterized by three key attributes:

  • Trust ($T$): The basic level of confidence in a participant's future actions.
  • Social Intimacy Degree ($r$): Derived from the frequency and content of interactions, distinguishing close friends from mere acquaintances.
  • Role Impact Factor ($\rho$): A measure of domain-specific expertise, ensuring recommendations come from relevant experts.
Social trust path model incorporating Trust (T), Social Intimacy (r), and Role Impact (ρ).

This model acknowledges that trust is non-linear; intimacy and reliability often attenuate rapidly as the number of "hops" in a chain increases. Modeling this attenuation reflects the real-world intuition that trust degrades over distance.

The MONTE_K Algorithm

The researchers introduced MONTE_K, a Monte Carlo-based approximation algorithm designed for efficient path selection. MONTE_K employs two primary optimization strategies to manage the search space:

  1. K-path Selection: Instead of exploring every possible neighbor at each step, the algorithm only considers the top $K$ candidates most likely to satisfy the constraints. This prevents the "search space explosion" common in dense networks.
  2. Dominating Node Optimization: The algorithm treats highly connected nodes as "checkpoints." If a simulation reaches a previously visited node, it compares the current path against the stored "best" path, retaining only the superior one.

By leveraging the power-law characteristics of social networks—where most nodes have few connections—MONTE_K can prune the search space aggressively without losing the optimal path.

Experimental Evaluation

The algorithm was tested using the Enron email corpus, which contains over 87,000 nodes and 300,000 links. This dataset allowed for the extraction of real-world social relationships and organizational roles essential for calculating Intimacy and Role Impact. The researchers compared MONTE_K against two other algorithms: H_MCOP and MCBA.

Comparison of Utility and Execution Time across sub-networks of varying sizes.

The results demonstrated that MONTE_K significantly outperforms its counterparts. In complex 6-hop networks, it achieved a utility (overall trustworthiness) up to 60.62% higher than H_MCOP. More impressively, MONTE_K offered massive speedups; in the largest tested sub-networks, its execution time was a small fraction of that required by H_MCOP, often identifying paths up to 35x faster.

Conclusion

MONTE_K provides a robust and scalable solution for navigating trust in complex social networks. By incorporating multi-dimensional QoT metrics and efficient Monte Carlo simulations, it identifies high-quality trust paths significantly faster than previous state-of-the-art methods. Future work aims to integrate this model into next-generation Customer Relationship Management (CRM) systems, effectively turning social network theory into a practical business tool for identifying trustworthy leads.

Summary updated

Abstract

Online social networks are becoming increasingly popular and are being used as the means for a variety of rich activities. This demands the evaluation of the trustworthiness between two unknown participants along a certain social trust path between them in the social network. However, there are usually many social trust paths between participants. Thus, a challenging problem is finding which social trust path is the optimal one that can yield the most trustworthy evaluation result. In this paper, we first present a new complex social network structure and a new concept of Quality of Trust (QoT) to illustrate the ability to guarantee a certain level of trustworthiness in trust evaluation. We then model the optimal social trust path selection as a Multi-Constrained Optimal Path (MCOP) selection problem which is NP-Complete. For solving this problem, we propose an efficient approximation algorithm MONTE_K based on the Monte Carlo method. The results of our experiments conducted on a real dataset of social networks illustrate that our proposed algorithm significantly outperforms existing approaches in both efficiency and the quality of selected social trust paths.
BibTeX
@inproceedings{liu2010optimal,
  author = {Guanfeng Liu and Yan Wang and Mehmet A. Orgun},
  title = {{Optimal Social Trust Path Selection in Complex Social Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7509},
}
Figure