Research On Trust Network Discovery And Trust Aggregation In Online Social Networks

With the development of the information technology, more and more socialized ap-plications are merging into peoples’daily life. These applications are not limited to the traditional social network sites (e.g. renren.com), but also involve the instant messaging, E-commerce and consumers’recommendation (e.g. wechat, taobao and dianping). Together with the popularization of the mobile computing techniques and devices, people can partic-ipate in theses socialized applications to share information, perform online transactions and collaborate with others. However, in such open, dynamic and large-scale online social net-works, users always encounter unfamiliar partners and such interactions imply uncertainties and risks. In such situations, trust plays an important role in the users’decision making process. Thus, the research on the trust inference in online social networks is significant.By describing the social network as a weighted digraph, the trust inference is the pro-cess of finding multiple trust propagation paths for the unfamiliar user pair and inferring their indirect trust relationship based on the propagation property of trust. Since the social networks are with the properties such as homogeneity, small-worldness and structural bal-ance etc., it is necessary to take into account these factors when making trust inferences in the online social networks. The first step of trust inference is to consider that what the optimal trust inference path is and how to find it. Then, how to maintain the direct trust relationships among the users taking account of the diversity of services and contexts. Fur-thermore, how to efficiently find multiple optimal or near optimal trust inference paths so as to enhance the accuracy of the trust inference. Finally, how to apply the trust discounting and fusion operations to the found paths in order to aggregate the trust originated from the source user to the target user and obtain the final trust inference result. Motivated by these questions, our research is carried out on the trust inference path search strategy and the op-timal trust inference path search method, trust subnetwork discovery based on multiple trust inference path search, context-aware direct trust relationship evaluation and trust inference path aggregation: Existing trust inference path search strategies mainly focus on how to maximize the inferred trust to the witnesses so as to improve the quality of the trust inference path, which ignores the role of distrust relationships in the trust inference. Based on the social structure balance theory, valuable information can be deduced with distrust relationships. However, not all the triads in the real-life social network are balanced. Thus, this paper first investi-gates the statistical characters of the balanced transitive triads and analyzes the social struc-ture balance characters of the trust discounting operators. Then, the inference path search strategies MIRBS and MIFUS are proposed, the optimal trust inference path search prob-lem is boiled down into the optimization problem and the optimal trust inference path search algorithm OTIPS is also detailed. Finally, the optimality of the path returned by OTIPS is proved theoretically. And the comparative experiments on the real-life large-scale data set also validate the superiority of the proposed trust inference search strategies and search al-gorithm on the trust inference path search efficiency and the trust inference accuracy.The propagation of trust along the path is based on the consistent trust scopes, i.e. the contexts of trust, along this path. It is difficult for users to find the interaction record with the same contexts for the forthcoming one because of the diversity of service con-texts, which is also known as the data sparsity problem. Traditional trust models do not pay enough attention to the contexts of trust. Although there are some context-aware trust models, the context description, contexts similarity measurement and maintenance of inter-action experience issues are not well solved. This paper gives a service oriented context description and contexts similarity measurement method, builds a context-aware direct trust relationship model and proposes a leader-follower based context-aware direct trust relation-ship evaluation approach. This method maintains a small-scale trust reference set to provide context-aware trust relationship evaluation and this reference set can update the contexts and adjusted trust value of the reference service according to the new interaction experi-ence. The simulation experiments show that the proposed method can utilize the contexts of the reference services to enhance trust evaluation accuracy when facing the data sparsity problem and acquire higher evaluation efficiency compared to existing context-aware trust relationship evaluation methods.After the determination of the trust inference path search strategy and the trust contexts, it is necessary to find multiple optimal or near optimal trust inference paths and construct the trust subnetwork. Existing trust inference path search approaches are mainly based on the classical brute-force path search algorithms with low search efficiency. Even there are some other novel stochastic approaches, but all theses methods ignore the structure characteristics of the social network, which leads to blind search and low efficiency. Moreover, the path search experience can not be accumulated or reused, and repeated search costs are consumed when facing repeated path search requests. This paper first proposes a SVD sign clustering based trust community detection method to find the structural characteristics of the trust network. Then, by taking each community of users as a colony of ants, the multiple ant colony optimization based trust subnetwork discovery algorithm ACO-TIPS is proposed. Finally, the comparative experiments on real data set validate the effectiveness of the trust community detection and the superiority of the proposed ACO-TIPS in trust inference path search efficiency and corresponding trust inference accuracy.When multiple trust inference paths are obtained and the trust subnetwork is construct-ed, how to apply appropriate trust discounting and fusion operations to these paths so as to obtain the final trust inference result. Existing trust discounting and fusion operators lack the comparison among different operators on the real data set and most trust aggregation methods ignore that the repeated computations of the same trust relationship along different trust inference paths will lead to the mass hysteria. This paper first gives the adaptive trust discounting operator taking into account the distribution characteristics of the balanced transitive triads and the partial dependent trust fusion operator taking into account the opinion confliction of different recommenders. Then, the flooding based adaptive trust inference path aggregation algorithm FATIPA is proposed. This algorithm spreads the trust from the source vertex to the whole trust subnetwork as a flood. When a vertex is flooded, the trust opinion of the source vertex about this vertex is deduced. This method does not require the elimination of dependent trust relationships in the trust subnetwork and also avoids the occurrence of the mass hysteria. Finally, the comparative experiments on real data set show that the proposed trust discounting and fusion operators yield higher trust inference accuracy and the trust inference path aggregation algorithm is also with lower time complexity and trust inference deviations.