The existed trust models have two shortages in searching the trust path:firstly, factors affecting the trust value were not considered fully in the searching, or considered the same. Meanwhile, many algorithms ignored the importance of the interaction number when searching the trust path. In view of these problems, a searching algorithm of trust path based on graph theory was proposed. The concept of probability of honesty was put forward to weigh the credibility of the node further, and as the searching priority basis, it is more reasonable in the priority searching. Meanwhile it searched by filtering and used probability of multi-factors which affect the credibility of the node. The analyses of algorithm show that the complexity of the proposed algorithm is (n-m)2 magnitude, much lower than the original fine-grained algorithm which complexity is n2 magnitude. The experimental results show that the proposed algorithm can better filter out malicious nodes, improve the accuracy of the trust path search algorithms, and resist the attacks of malicious nodes.
