Research On Dynamic Bidirectional Heuristic Trust Path Search Algorithm

The rapid development of online social networks and media has greatly promoted people’s online interaction.However,as more and more users transfer their interaction to the social network,the network becomes more complex,and even the phenomenon of information overload occurs in it.Compared with the traditional network,the new one makes users much more difficultly identify and avoid spam information and evaluate the reliability of information.Therefore,it is necessary to introduce the trust mechanism to help users make more correct decisions.An overall or local trust network can be set by the trust relationship of users,which can solve the problem of information overload.For users without direct interaction,the intuitive solution is to find a feasible trust path from the source user to the target user for trust propagation.The length of trust path and the selection of search method become the key problems in the search process of reliable trust path.However,the traditional trust path search algorithms are based on the unidirectional search algorithm for trust propagation,which leads to a long time for finding the path;on the other hand,the number of trust paths and the accuracy of trust prediction are reduced by setting the trust threshold and limiting the search width.Based the above problems,it is a challenge to quickly search and form the reliable and optimal indirect trust relationship.This paper proposes a dynamic bidirectional heuristic trust path search algorithm,which aims to solve the problem of finding the reliable trust path by studying the heuristic search.Firstly,some longer paths but with higher trust values are considered more trusted,which is based on that the path length is not the only determinant.Therefore,the acceptable path set will be found based on the six dimensional space theory after the shortest path is found.Then,the MM(Meet in the middle,MM)algorithm is improved by introducing the adjustment factor,which can dynamically allocate the search weight of the search tree.In this way,the search process can be carried out in a smaller direction,and the search efficiency can also be improved.Finally,the trust degree will be predicted along the searched reliable trust path,and the final trust value is output.The results of experiment show that the accuracy and efficiency of trust prediction of the proposed algorithm are better than other algorithms.Furthermore,a dynamic anytime cost bounded search algorithm is also proposed in this paper.Firstly,the acceptable cost bound is obtained by setting the dynamic weighted factor to weight the current optimal cost,so as to quickly find a solution.Then,the current cost bound will be reduced in every iteration to improve the current solution until the time out.The results of experiment show that the proposed algorithm effectively improves the search efficiency of the existing algorithms.