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
1531246938 2101902057 1923357748 2104661673 1922376695 2073926352 2510391126 2142633542 2017992786
In open settings, the participants are autonomous and there is no central authority to ensure the felicity of their interactions. When agents interact in such settings, each relies upon being able to model the trustworthiness of the agents with whom it interacts. Fundamentally, such models must consider the past behavior of the other parties in order to predict their future behavior. Further, it is sensible for the agents to share information via referrals to trustworthy agents. Much progress has recently been made on probabilistic trust models including those that support the aggregation of information from multiple sources. However, current models do not support trust updates, leaving updates to be handled in an ad hoc manner. This paper proposes a trust representation that combines probabilities and certainty (defined as a function of a probability-certainty density function). Further, it offers a trust update mechanism to estimate the trustworthiness of referrers. This paper describes a testbed that goes beyond existing testbeds to enable the evaluation of a composite probability-certainty model. It then evaluates the proposed trust model showing that the trust model can (a) estimate trustworthiness of damping and capricious agents correctly, (b) update trust values of referrers accurately, and (c) resolve the conflicts in referral networks by certainty discounting. Semantic Web endeavors have mainly focused on issues pertaining to knowledge representation and ontology design. However, besides understanding information metadata stated by subjects, knowing about their credibility becomes equally crucial. Hence, trust and trust metrics, conceived as computational means to evaluate trust relationships between individuals, come into play. Our major contributions to semantic Web trust management are twofold. First, we introduce our classification scheme for trust metrics along various axes and discuss advantages and drawbacks of existing approaches for semantic Web scenarios. Hereby, we devise our advocacy for local group trust metrics, guiding us to the second part which presents Appleseed, our novel proposal for local group trust computation. Compelling in its simplicity, Appleseed borrows many ideas from spreading activation models in psychology and relates their concepts to trust evaluation in an intuitive fashion. This paper investigates the role of trust metrics in attack-resistant public key certification. We present an analytical framework for understanding the effectiveness of trust metrics in resisting attacks, including a characterization of the space of possible attacks. Within this framework, we establish the theoretical best case for a trust metric. Finally, we present a practical trust metric based on network flow that meets this theoretical bound. Trust propagation is the principle by which new trust relationships can be derived from pre-existing trust relationship. Trust transitivity is the most explicit form of trust propagation, meaning for example that if Alice trusts Bob, and Bob trusts Claire, then by transitivity, Alice will also trust Claire. This assumes that Bob recommends Claire to Alice. Trust fusion is also an important element in trust propagation, meaning that Alice can combine Bob's recommendation with her own personal experience in dealing with Claire, or with other recommendations about Claire, in order to derive a more reliable measure of trust in Claire. These simple principles, which are essential for human interaction in business and everyday life, manifests itself in many different forms. This paper investigates possible formal models that can be implemented using belief reasoning based on subjective logic. With good formal models, the principles of trust propagation can be ported to online communities of people, organisations and software agents, with the purpose of enhancing the quality of those communities. This research aims to develop a model of trust and reputation that will ensure good interactions amongst software agents in large scale open systems in particular. The following are key drivers for our model: (1) agents may be self-interested and may provide false accounts of experiences with other agents if it is beneficial for them to do so; (2) agents will need to interact with other agents with which they have no past experience. Against this background, we have developed TRAVOS (Trust and Reputation model for Agent-based Virtual OrganisationS) which models an agent's trust in an interaction partner. Specifically, trust is calculated using probability theory taking account of past interactions between agents. When there is a lack of personal experience between agents, the model draws upon reputation information gathered from third parties. In this latter case, we pay particular attention to handling the possibility that reputation information may be inaccurate. Recently, there has been tremendous interest in the phenomenon of influence propagation in social networks. The studies in this area assume they have as input to their problems a social graph with edges labeled with probabilities of influence between users. However, the question of where these probabilities come from or how they can be computed from real social network data has been largely ignored until now. Thus it is interesting to ask whether from a social graph and a log of actions by its users, one can build models of influence. This is the main problem attacked in this paper. In addition to proposing models and algorithms for learning the model parameters and for testing the learned models to make predictions, we also develop techniques for predicting the time by which a user may be expected to perform an action. We validate our ideas and techniques using the Flickr data set consisting of a social graph with 1.3M nodes, 40M edges, and an action log consisting of 35M tuples referring to 300K distinct actions. Beyond showing that there is genuine influence happening in a real social network, we show that our techniques have excellent prediction performance. Recommender Systems (RS) suggest to users items they will like based on their past opinions. Collaborative Filtering (CF) is the most used technique and works by recommending to the active user items appreciated by similar users. However the sparseness of user proles often prevent the computation of user similarity. Moreover CF doesn’t take into account the reliability of the other users. In this paper 1 we present a real world application, namely moleskiing.it, in which both of these conditions are critic to deliver personalized recommendations. A blog oriented architecture collects user experiences on ski mountaineering and their opinions on other users. Exploitation of Trust Metrics allows to present only relevant and reliable information according to the user’s personal point of view of other authors trustworthiness. Dieren tly from the notion of authority, we claim that trustworthiness is a user centered notion that requires the computation of personalized metrics. We also present an open information exchange architecture that makes use of Semantic Web formats to guarantee interoperability between ski mountaineering communities. 1 This work is based on an earlier work: Trust-enhanced Recommender System The World Wide Web has transformed into an environment where users both produce and consume information. In order to judge the validity of information, it is important to know how trustworthy its creator is. Since no individual can have direct knowledge of more than a small fraction of information authors, methods for inferring trust are needed. We propose a new trust inference scheme based on the idea that a trust network can be viewed as a random graph, and a chain of trust as a path in that graph. In addition to having an intuitive interpretation, our algorithm has several advantages, noteworthy among which is the creation of an inferred trust-metric space where the shorter the distance between two people, the higher their trust. Metric spaces have rigorous algorithms for clustering, visualization, and related problems, any of which is directly applicable to our results. 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.