Research On Personalized Trust Evaluation In Online Social Networks

With the rapid development of networking techniques and the prevalence of network applications, online social networks (OSNs) have become the most popular tools and platforms for people's social activities, including making new friends, conducting daily communication or product recommendation, and so on. In the dynamic, open and large scale online social applications, in order to encourage users'good behavior, help users choose proper partners and decide whether to conduct further interactions (e.g., information exchange or product recommendation), improve their service using experience, and guarantee the normal function of the whole system, it is very necessary to estimate the trust levels among users. Personalized trust evaluation is proposed exactly for this aim, which has an important value of both theory and practice.Existing trust models in other related fields (e.g., P2P network, multi agent system, or semantic network) cannot be directly applied into online social networks, due to the following issues:1) Existing algorithms usually assume that there is an existing small trusted graph, for which little work has been done; moreover, information used for constructing trust is usually subjective and dynamically changing, which make it difficult to collect or maintain.2) Trust models usually overlook the features of user behavior and the mutual influence between users. Actually, the degree that a user is being trusted is closely related with his social influence. Therefore, studying how to differentiate users' social influence is meaningful to the construction of a comprehensive trust model.3) Graph-based trust models cannot well address the two challenges of path dependence and trust decay. That is, when multiple trusted paths are overlapped with each other, how will the model choose trust information on those paths? And how will the trust decay through the propagation process?4) One of the most important application scenarios of trust evaluation is trust-based recommendation system. In those systems, predicting users'ratings is usually being taken as a static process, which is inconsistent with real life. To address those issues, we study the frontier researches in social network analysis and trust evaluation techniques, and we try to discover the latent rules and dynamic features among trust mechanism, network structure, and user behaviors. In this dissertation, we focus on the trust evaluation models and algorithms in online social networks.Specifically, the contributions of this dissertation are fourfold:(1) We propose a small world network theory-based trusted graph generation framework, SWTrust. Existing trust algorithms take the base of a small trusted graph, and the information used to construct trust is usually too complicated to get or maintain, and usually subjective and changeable, which make it vulnerable to vicious nodes. With those problems in mind, we use the small-world network characteristics of online social networks and taking advantage of "weak ties", to divide users'neighbors into three categories based on their active domains: local neighbors, longer contacts, and the longest contacts. When conducting breadth-first search algorithms, we select the next hop neighbors uniformly among the above three categories. In this way, the coverage can be guaranteed and the efficiency can be improved. In addition, comparing to other subjective information, user domain is relatively objective and cannot be changed at will, which makes SWTrust more robust.(2) We propose a fine-grained feature-based social influence evaluation model, FBI. In real life, trust and influence can impact each other:influential people are likely to be trusted by others, while trusted friends have more chance and strength to influence a person. First, we construct a user's initial social influence by exploring two essential factors, that is, the possibility of impacting others, and the importance of the user himself. Second, we design the social influence adjustment model based on the PageRank algorithm by identifying the influence contributions of friends. For the aim of fine-grained evaluation, based on a feature set which includes the related topics and user profiles, we differentiate the feature strength of users and the tie strength of user relations. We also emphasize the effects of common neighbors in conducting influence between two users. Through experimental analysis, our FBI model shows remarkable performance, which can identify all users'social influences with much less duplication (it is less than7%with our model, while more than80%with other degree-based models), while having a larger influence spread with top-k influential users. A case study validates that our model can identify influential users with higher quality.(3) We design a generalized flow based trust evaluation algorithm, GFTrust. In online social networks (OSNs), to evaluate trust from one user to another indirectly connected user, the trust information in the trusted paths (i.e., paths built through intermediate trustful users) should be carefully treated. Some paths may overlap with each other, which lead to a unique challenge of path dependence, i.e., how to aggregate the trust values of multiple dependent trusted paths. OSNs bear the characteristic of high clustering, which makes the path dependence phenomenon usually happen. Another challenge is trust decay through propagation, i.e., how to propagate trust along a trusted path, considering the possible decay in each node. We analyze the similarity between trust propagation and network flow, and convert a trust evaluation task (with path dependence and trust decay) into a generalized network flow problem. We propose a modified flow-based trust evaluation scheme GFTrust, in which we address path dependence using network flow, and model trust decay with the leakage associated with each node. Experimental results, with the real social network data sets of Epinions and Advogato, demonstrate that GFTrust can predict trust in OSNs with a high accuracy, and verify its preferable properties.(4) We also design a Fluid dynamics theory based time-evolving rating prediction scheme, FluidRating. The goal of a trust-based recommendation system is to predict unknown ratings based on the ratings expressed by trusted friends. However, most of the existing work only considers the ratings at the current time slot. In real life, a user receives the influence of different opinions sequentially; accordingly, his opinion evolves over time. We propose a novel rating prediction scheme, FluidRating, which uses fluid dynamics theory to reveal the time-evolving formulation process of human opinions. The recommendation is modeled as fluid with two dimensions:the temperature is taken as the "opinion/rating," and its volume is deemed as the "persistency," representing how much one insists on his opinion. When new opinions come, each user refines his opinion through a round of fluid exchange with his neighbors. Opinions from multiple rounds are aggregated to gain a final prediction; both uniform and non-uniform aggregations are tested. Moreover, three sampling approaches are proposed and examined. The experimental evaluation of a real data set validates the feasibility of the proposed model, and also demonstrates its effectiveness.