Finding a good clustering of vertices in a network, where vertices in the same cluster are more tightly connected than those in different clusters, is a useful, important, and well-studied task. Many clustering algorithms scale well, however they are not designed to operate upon internet-scale networks with billions of nodes or more. We study one of the fastest and most memory efficient algorithms possible - clustering based on the connected components in a random edge-induced subgraph. When defining the cost of a clustering to be its distance from such a random clustering, we show that this surprisingly simple algorithm gives a solution that is within an expected factor of two or three of optimal with either of two natural distance functions. In fact, this approximation guarantee works for any problem where there is a probability distribution on clusterings. We then examine the behavior of this algorithm in the context of social network trust inference.
There are many trust inference algorithms that take advantage of given trust values and the structure of a social network, including Advogato @cite_26 , Appleseed @cite_37 , Sunny @cite_11 , and Moletrust @cite_27 . These algorithms use trust that is assigned on a continuous scale (e.g. 1-10). Trust can also be treated as a probability. This approach has been used in a number of algorithms, including @cite_35 @cite_31 @cite_0 @cite_32 . The difficulty of generating these probabilities, using influence as a proxy for trust, was addressed in @cite_19 . In our research, we work with probabilities that are given , but those derived from other methods could also be used in our algorithms.
@cite_35 @cite_37 @cite_26 @cite_32 @cite_0 @cite_19 @cite_27 @cite_31 @cite_11
2017992786 2291511137 2056732180 2064516952
In this article, we describe a new approach that gives an explicit probabilistic interpretation for social networks. In particular, we focus on the observation that many existing Web-based trust-inference algorithms conflate the notions of “trust” and “confidence,” and treat the amalgamation of the two concepts to compute the trust value associated with a social relationship. Unfortunately, the result of such an algorithm that merges trust and confidence is not a trust value, but rather a new variable in the inference process. Thus, it is hard to evaluate the outputs of such an algorithm in the context of trust inference. This article first describes a formal probabilistic network model for social networks that allows us to address that issue. Then we describe SUNNY, a new trust inference algorithm that uses probabilistic sampling to separately estimate trust information and our confidence in the trust estimate and use the two values in order to compute an estimate of trust based on only those information sources with the highest confidence estimates. We present an experimental evaluation of SUNNY. In our experiments, SUNNY produced more accurate trust estimates than the well-known trust inference algorithm TidalTrust, demonstrating its effectiveness. Finally, we discuss the implications these results will have on systems designed for personalizing content and making recommendations. The rise of social network and crowdsourcing platforms makes it convenient to take advantage of the collective intelligence to estimate true labels of questions of interest. However, input from workers is often noisy and even malicious. Trust is used to model workers in order to better estimate true labels of questions. We observe that questions are often not independent in real life applications. Instead, there are logical relations between them. Similarly, workers that provide answers are not independent of each other either. Answers given by workers with similar attributes tend to be correlated. Therefore, we propose a novel unified graphical model consisting of two layers. The top layer encodes domain knowledge which allows users to express logical relations using first-order logic rules and the bottom layer encodes a traditional crowdsourcing graphical model. Our model can be seen as a generalized probabilistic soft logic framework that encodes both logical relations and probabilistic dependencies. To solve the collective inference problem efficiently, we have devised a scalable joint inference algorithm based on the alternating direction method of multipliers. Finally, we demonstrate that our model is superior to state-of-the-art by testing it on multiple real-world datasets. In Service-Oriented Computing environments, there is a large number of service providers providing a variety of services to service customers. Conventional recommender systems, which adopt the information filtering techniques, can be used to automatically generate recommendations of service providers to service customers who are also the system users. However, data sparsity and trust enhancement are the traditional problems in recommender systems. Targeting the data sparsity problem, recent studies on recommender systems have started to leverage information from online social networks to collect recommendations from more participants and derive the final recommendation. However, this requires the methods to infer the trust between participants without any direct interactions in online social networks, which should take into account both the social context of participants and the context of the target services to be recommended, for trust enhanced recommendations. In this paper, we first present a contextual social network model that takes into account both participants' personal characteristics (referred to as the independent social context, including preference and expertise in domains) and mutual relations (referred to as the dependent social context, including the trust, social intimacy, and interaction context between two participants). In addition, we propose a new probabilistic approach, SocialTrust, as the first solution in the literature, to social context-aware trust inference in social networks. The result delivered by this approach is particularly important in evaluating the trust from a source participant to an end recommender who recommends a target service or service provider, via the sub-network consisting of intermediate participants recommenders between them and relevant contextual information. Moreover, we propose algorithms that consider cycles and information updates in social networks. Experiments demonstrate that our approach is effective and superior to existing trust inference methods, and can deliver more reasonable and trustworthy results. The proposed algorithms considering cycles and information updates in social networks are efficient and applicable to real social networks. Abstract Given the increasing applications of service computing and cloud computing, a large number of Web services are deployed on the Internet, triggering the research of Web service recommendation. Despite of service QoS, the use of user feedback is becoming the current trend in service recommendation. Likewise in traditional recommender systems, sparsity, cold-start and trustworthiness are major issues challenging service recommendation in adopting similarity-based approaches. Meanwhile, with the prevalence of social networks, nowadays people become active in interacting with various computers and users, resulting in a huge volume of data available, such as service information, user-service ratings, interaction logs, and user relationships. Therefore, how to incorporate the trust relationship in social networks with user feedback for service recommendation motivates this work. In this paper, we propose a social network-based service recommendation method with trust enhancement known as RelevantTrustWalker. First, a matrix factorization method is utilized to assess the degree of trust between users in social network. Next, an extended random walk algorithm is proposed to obtain recommendation results. To evaluate the accuracy of the algorithm, experiments on a real-world dataset are conducted and experimental results indicate that the quality of the recommendation and the speed of the method are improved compared with existing algorithms.