Multiple QoT Constrained Social Trust Path Selection in Complex Social Networks

In recent years, online social networks with numerous participants have been used as the means for rich activities, where trust is one of the most important indications for participants´ decision making, demanding the evaluation of the trustworthiness of a target participant along a certain social trust path from a source participant. However, there are usually many social trust paths between participants. Thus, a challenging problem is how to select the optimal one from massive social trust paths yielding the most trustworthy trust evaluation result based on participants trust evaluation criteria. To address this issue, in this paper, we first propose a new Multiple QoT Constrained Social Trust Path (MQCSTP) selection model which considers both adjacent constraints and end-to-end constraints, based on a novel concept Quality of Trust (QoT) and a novel complex social network structure. We then model the MQCSTP selection as the classical NP-Complete Multi-Constrained Optimal Path (MCOP) selection problem. For solving this problem, we propose an effective and efficient heuristic algorithm, called H_MQCSTP. The results of our experiments conducted on a real dataset of online social networks illustrate that the proposed method outperforms existing models in both efficiency and the quality of delivered solutions.