State Of The Art/Trust Reputation And Social Network Analysis

From LiquidPubWiki

Jump to: navigation, search

Contents

Introduction

Being able to automatically provide a 'fair' credit attribution to both peers (such as authors, reviewers, etc.) and liquid publications (or SKOs) alike is crucial to the success of this new publication paradigm.

Numerous trust and reputation mechanisms already exist in the literature. These usually rely on several sources of information for computing reputation, which may roughly be grouped into three categories [1]:

  • Direct information from personal past experience with the peer in question
  • Indirect information from the past experience of third party members of the network with the peer in question
  • Socio-cognitive information, such as the belief in the willingness, capability, and persistence of the peer in question in carrying out a certain action.

To our knowledge, the majority of research in this field has focused mainly on the outcome of previous interactions, whether this information has been obtained directly from personal experience or indirectly from the experience of other members in the network. Only a few have focused on other sources of information. For example, Castelfranchi and Falcone (2000)[2] and Brainov and Sandholm (1999)[3] have focused on a cognitive view of trust.

In the LiquidPub paradigm, we believe it is critical to guarantee the fairness of the system by detecting redundant ratings, consistent biases, deliberately distorted ratings, unreliable reviewers, etc. To achieve this, we believe that social relationships, along with other social network measurements, should be considered in addition to direct and indirect information from previous experiences.

The remainder of this section is divided into the following three sub-sections. The first sub-section provides a background on the available literature on computational trust and reputation models. The second sub-section provides a brief overview on social network analysis. The third, and last, sub-section provides an introduction to the available literature on the use of social networks for computing reputation. In our literature review, we naturally focus only on the available research that we believe is most relevant to our work.


Computational Trust and Reputation Models

The scientific research in the area of computational trust and reputation mechanisms is a recent discipline oriented to increase the reliability and performance of electronic communities by introducing in such communities these well known human social control mechanisms. There are several reviews in the literature [4][5] that analyse and compare the increasing amount of models that have appeared during the last few years. These models, apart from the mechanisms used to calculate the trust and reputation values, also differ in the very essence of what is trust and reputation. In this section we will present a general taxonomy that will help us to determine which are the type of models that are more interesting for the LiquidPub project. Finally we will present briefly some of these models.

There are two kinds of social evaluations that play an essential role in trust and reputation models: image and reputation. Both social evaluations concern other agents' (targets) attitudes toward socially desirable behaviour, and may be shared by a multitude of individuals. Image is an evaluative belief and it tells that the target is “good” when it displays a certain behaviour, and that it is “bad” in the opposite case. Reputation is instead a shared voice, i.e. a belief about others saying that a given target enjoys or suffers from a shared image. In other words, reputation is true when it is actually spread, not when it is accurate. From now on, we will define reputation as the group opinion on (what is said about) someone (or something) playing a specific role.

Image is subjective by nature. Two individuals, even if they have observed the same interactions can have a completely different image of a target. Image depends on the personal experiences of the individual but also on other internal elements like for example the goals the individual has.

In the case of reputation we find two ways of looking at it:

  • What we call subjective reputation, which as the name suggests, is also subjective in a similar way image is. Models that consider reputation as a subjective property assume that every individual can have a different method to calculate the reputation values. Also, you cannot assume that all members of the society have the same knowledge. Given that, the reputation value will depend on who is calculating that value. Examples of models that follow this approach are ReGreT [6], RepAge [7], Sierra-Debenham model [8], AFRAS [9], FIRE [10] among others.
  • What we call global reputation. In this case, the approach assumes there is a shared (and agreed) method to calculate the reputation values and that this calculation is performed over the same set of elements that are public and therefore available to all the individuals. In this case, we can say that each individual has a public reputation in front of the society because the calculation does not depend on who is the evaluator. Usually, these models rely on a central service that is responsible of calculating the reputation values, although this centrality is not strictly necessary if we can guarantee that each individual is using the same method and data to make the calculations. Examples of models that follow this approach are those used in on-line auctions like eBay [11] or Amazon Auctions [12], laboratory models like Sporas [13] and web related methods (based on network analysis) like PageRank [14], HITS [15], or TrustRank [16].

In the LiquidPub project we are looking for mechanisms to rate different elements that go from SKOs to reviewers or authors. These ratings must be public and transparent so any individual knows where they come from so they can redo the calculations obtaining exactly the same results. Given that, what we need in the LiquidPub project is what we have defined as global reputation models. Both image and subjective reputation are not useful in this specific context.

What is clear also is that a single method to calculate reputation is not enough. Even for calculating the reputation of an individual in a specific role we will have to provide different mechanisms to calculate the reputation, each one stressing a different aspect of the interactions. This set of methods has to be public and available for every individual.

We will present now some the models that we think can be relevant in the LiquipPub project.

Online reputation mechanisms: eBay, Amazon Auctions and OnSale

eBay [11], Amazon Auctions [12] and OnSale Exchange [17] are good examples of online marketplaces that use reputation mechanisms. eBay is one of the world’s largest online. Most items on eBay are sold through English auctions and the reputation mechanism used is based on the ratings that users perform after the completion of a transaction. The user can give three possible values: positive(1), negative(-1) or neutral(0). The reputation value is computed as the sum of those ratings over the last six months. Similarly, Amazon Auctions and OnSale Exchange use also a mean (in this case of all ratings) to assign a reputation value.

All these models consider reputation as a global property and use a single value that is not dependent on the context. The information source used to build the reputation value is the information that comes from other agents that previously interacted with the target agent (witness information). They do not provide explicit mechanisms to deal with users that provide false information. A great number of opinions that “dilute” false or biased information is the only way to increase the reliability of the reputation value. In [18] Dellarocas points out that the commercial success of online electronic markets suggests the models have achieved their primary objective: ‘generate sufficient trust among buyers to persuade them to assume the risk of transacting with complete strangers’.

Certainly these reputation mechanisms have contributed to the success of e-markets like eBay but what is not clear is to which extend. There are several studies that try to analyze the properties of these models specially based on eBay data sets (see again [18]).

Sporas

Sporas [13] is an evolved version of the online reputation models. In this model, only the most recent rating between two users is considered. Another important characteristic is that users with very high reputation values experience much smaller rating changes after each update than users with a low reputation. Using a similar approach to the Glicko [19] system —a computational method used to evaluate the player’s relative strengths in pairwise games—, Sporas incorporates a measure of the reliability of the users’ reputation based on the standard deviation of reputation values. This model has the same general characteristics as the previously commented online reputation mechanisms. However, it is more robust to changes in the behaviour of a user and the reliability measure improves the usability of the reputation value.

PageRank

PageRank [14] is a patent by Google. The mechanism is inspired in how the number of citations determine the relevance of a paper in the scientific community. As the authors say in the description of the patent "PageRank is a method that assigns importance ranks to nodes in a linked database, such as any database of documents containing citations, the world wide web or any other hypermedia database". The main idea behind PageRank is to interpret a link from one page A to a page B as a vote from page A for page B. PageRank also takes into account the PageRank value of the page that casts the vote.

The formula used by PageRank is the following:

PR(A) = (1-d) + d \left( \frac{PR(T1)}{C(T1)} + ... + \frac{PR(Tn)}{C(Tn)}\right)

where:

PR(A) Is the PageRank of page A.

PR(Ti) Is the PageRank of pages Ti that link page A.

C(Ti) Is the number of exit links from page Ti.

d is a constant between 0 and 1.

HITS

Like PageRank, the HITS [15] mechanism is used to evaluate the relevance of a web page according to the link's network. However, instead of using all the WWW like PageRank, the link relations that are taken into account are those associated with what they call 'authority' pages. This idea is based on the 'Abundance Problem', that is, "the number of pages that could reasonably be returned as relevant is far too large for a human user to digest". Therefore, instead of using any page that links to the target page, we first select a subset of 'authority' pages and these subset is what will be used to make the calculations. The authors present an algorithm to determine this subset of pages. They define also the concept of 'hub'. A 'hub' is a page that have links to multiple relevant authoritative pages.

Given that, each page has associated two values: its authority value and its hub value.

Particularities: It is executed at query time, not at indexing time, with the associated hit on performance that accompanies query-time processing. It is not commonly used by search engines. It computes two scores per document, hub and authority, as opposed to a single score.

Social Network Analysis: an Overview

Social network analysis may be defined as a set of methods for analysing social structure by investigating relational aspects of these structures. Social networks are composed of vertices (or nodes) and edges. A vertex is the fundamental unit of a network. It usually represents people or groups of people (e.g. organizations). An edge is a link connecting two vertices. It represents relational data, such as kinship, friendship, colleagueship, scientific collaboration, etc.

Different types of networks may exist based on the different types of vertices and/or edges. For instance, vertices in a network may be either of the same type or different types (e.g. representing different nationalities). Similarly, edges in a network may also be of the same type or of different types (e.g. representing friendship and animosity). Additionally, vertices and edges may be given weights. For example, a weight of a vertex may represent how important is the person in its community. A weighted edge may provide better insight on the strength of the friendship between two people. Finally, edges may also be directed, i.e. pointing in one direction. This would be useful, for example, to represent the direction of email messaging between people.

In our research, we are interested in the analysis of such networks. In what follows, we provide an overview of the most common network properties that may be computed, as summarized by Newman (2003)[20]. We divide these into two categories: properties of a vertex in a given network and properties of a network.

Properties of a Vertex

  • Degree Centrality:
    This is a measure of the number of connections (or edges) a vertex has. This measure illustrates the connectivity of a vertex in a network.
  • Closeness Centrality (or Efficiency of a Vertex):
    This is a measure of the mean shortest (or geodesic) distance between one vertex and all others in a network. This illustrates how close a vertex is from others in the network.
  • Betweenness Centrality:
    This is a measure of the number of shortest paths (or geodesic paths) that pass through one vertex. The shortest path between any two vertices in a network is computed. Then the total number of shortest paths that pass through a given vertex is deduced. This measure may illustrate the importance of a vertex in a network.
  • Eigenvector Centrality (or Prestige Degree):
    This is a measure of the percentage of vertices referencing the vertex in question. Google's PageRank algorithm is one example of computing the prestige degree. This measure may also illustrate the importance of a vertex in a network.

Properties of a Network

  • Small-World Effect:
    A network is said to experience a small-world phenomenon if most pairs of vertices are connected by a short path through the network. The measure of the small-world effect is obtained by computing the mean geodesic distance between vertex pairs in a network.
  • Network Navigation:
    It has been pointed out by Kleinberg (2000)[21] that having short paths in a network is useful; however, it is also important for people to be able to find and use these existing short paths. This is what is referred to as network navigation.
  • Transitivity (or Clustering):
    The transitivity property is defined as follows: 'If vertex A is connected to vertex B and vertex B to vetex C, then there is a heightened probability that vertex A will also be connected to vertex C'[20]. The measure of transitivity of a network is obtained by computing a clustering coefficient, which is based on computing the triangles, connecting three vertices together, in a network. This measure may also be used to describe network density.
  • Degree Distribution:
    Let pk be the fraction of vertices in the network that have a degree k. Therefore, pk may be viewed as the probability that a randomly chosen vertex has a degree k. The degree distribution of a network is then defined as a distribution of these probabilities in a network.
  • Mixing Patterns (or Assortative Mixing):
    Mixing patterns describe which vertices link with which others. Usually, the probability of connection between vertices depends on the types of the vertices. Assortative mixing is then defined as the selective linking between vertices based on their types.
  • Degree Correlations:
    Degree correlations are a special type of assortative mixing. In this type, vertices link to others based on the degree centrality of each. For example, sometimes vertices with high degrees link to other vertices with high degrees. In other networks, vertices with high degree may prefer to link to vertices with low degrees.
  • Community Structure (or blockmodels):
    Networks are said to show community structures if there exists groups of vertices that have a high density of edges between them, while lower density of edges exist between different groups. The resulting groups of vertices are sometimes referred to as clusters. Networks with assortative mixing may also show community structure. But this is not necessarily the case. If a network shows assortative mixing but no community structure, then the network is labelled as a 'stratified' network.
  • Giant Component:
    The giant component is the largest component, or the largest cluster, in the network. It is sometimes useful to calculate the size of the giant component and the percentage of the entire network that it covers.
  • Network Resilience:
    This is a measure of the robustness of the network to the removal of vertices. This measure is usually related to the degree distribution of a network. For example, most networks are robust against the random removal of vertices, but not to the selective removal of vertices with high degrees. The betweenness centrality and the eigenvector centrality (or the prestige degree) of vertices usually provide insight to a network's resilience.


Literature Review: Social Networks and Reputation

In what follows, we present an overview of the selected literature on social networks and reputation that we believe is most related to our work in the LiquidPub project.

Finding the Best Connected Scientist via Social Network Analysis

Newman (2001) [22] focuses on the properties of coathorship networks for choosing the best connected scientist. The study focused on the Physics E-print Archive database from 1992 to the present, the Medline database from 1961 to the present, the SPIRES database from 1974 to the present, and the NCSTRL database for the last ten years.

The following basic results where automatically computed:

  • number of authors
  • number of papers per author
  • number of authors per paper
  • number of collaborators per author
  • size of the giant component (i.e. the connected subset of vertices whose size scales extensively), and the percentage of the entire network that this giant component covers
  • clustering coefficient of the network
  • shortest path between two nodes
  • betweenness centrality of a node
  • average distances between nodes

The paper also shows how weighted collaboration networks may be used to measure the closeness of collaborative ties and who is the best connected scientist. The idea is that the number of papers each pair of scientists coauthored and how many other coauthors are on those papers affect the strength of coauthorship ties. The distance between two scientists becomes an inverse of the weight of their collaborative ties. This new distance definition is then used in computing the best connected scientist.


Searching for Relevant Publications via an Enhanced P2P Search

In the work done by Chirita et al. (2005)[23], a P2P search strategy is enhanced with social network analysis to improve the search. Their work was applied to scientific collaboration networks to improve keyword search for relevant publications.

For selecting the peers to forward the query to, three strategies are introduced. The first makes use of the peer's connectivity in the network. The second makes use of the peer's reputation. This could be a Pagerank or any other simple metric. The third makes use of the similarity between the chosen peer and the querying one. Hybrid models may then be constructed using these three models.

The results show that the best outcome is achieved when choosing peers based on the relative similarity ratio. Also, increasing the number of chosen similar peers to a number larger than 3 does not provide an impressive increase in performance. Finally, it turns out that combining the similarity and connectivity based strategies does not improve performance! This implies that the best connected peers are not necessarily the repository of the best resources in the network.


Using Social Relationships for Computing Reputation

In the work done by Sabater and Sierra (2002)[24], social network analysis, which is based on studying the social relationships between peers, is used to provide an additional source of information (to traditional information obtained from direct interactions and those obtained from other members of the society about their past experiences) for computing reputations. The basic idea of the system is that reputation is based on three dimensions: the individual dimension, the social dimension, and the ontological dimension.

The individual dimension models the direct interactions between two agents. In this dimension, the subjective reputation is calculated directly from an agent's impressions database. However, the reputation value on its own is not sufficient. Hence a reliability measure of this value is also calculated by taking into account the number of impressions used to calculate the reputation value and the variability of their rating values.

The social dimension models the case when the source of information comes from other agents in the system. Depending on the information source, three types of social reputations arise: witness reputation, neighbourhood reputation, and system reputation.

In witness reputation, to identify witnesses, first the most connected sub-graphs are obtained, then the nodes with local centrality are identified. This way the peer will end up using only the most representative agents for its source of information; hence, it will be minimizing the correlated evidence problem. The next step would be to aggregate all this witness information. The final reputation measure would be an aggregation of the reputation values provided by all witnesses, taking into account how much trustworthy is each witness in providing its reputation value of the target agent. The final reliability measure is also an aggregation of the reliability and trust measures of each individual witness. The trust measure is defined as follows. The degree of trust that an agent ‘a’ has in agent ‘b’ on providing feedback about agent 'c' is a combination of subjective trust reputations, which are calculated in a similar manner to individual reputation, and social trust. As for social trust measures, these are the results of applying fuzzy rules. These fuzzy rules depend on the type of relationships in a specific scenario, such as competitive, cooperative, and trade relationships. Note that different fuzzy rules would exist for different contexts and scenarios.

The basic idea of neighbourhood reputation is that the reputation of a peer's neighbour, along with the type of relationship that exists between the two (e.g. competitive versus cooperative relationships), can give an idea about to the reputation of the target peer itself. Again, fuzzy rules, which are domain dependent, are used to generate the reputation of the target peer based on the reputation of its neighbour and their relationship type. The reputations obtained from investigating the reputations of all neighbours are aggregated, using the reliability of each neighbour, to obtain one final reputation value. Similarly, the reliability of all neighbours are also aggregated into one final reliability value.

As for the system reputation, it is a default reputation value obtained from the observable role an agent plays in a given institutional structure. It is domain dependent and part of the initial knowledge of the agent. This observable feature is what differs system reputation from other social structures.

Finally, different reputation types may combine in such a way resulting in new reputations. For instance, to have the reputation of a swindler seller, one should have the reputation of overcharging items and the reputation of delivering items with a poor quality. This model is what the authors refer to as the ontological dimension. When one reputation concept is the parent node of two or more reputation concepts in the ontological tree, then both the reputation and reliability measures of the parent node become a combination of the reputation and reliability measures of the children nodes.

The final reputation and reliability measures are defined as a combination of those of the individual dimension, the social dimension, and the ontological dimension. Agents have the option of deciding which dimension may be more relevant. For instance, if the agent does not have enough information, then it can decide that the social dimension will be most relevant.


Identifying, Categorizing, and Analysing Social Relations for Trust Evaluation

As we have seen above, more robust reputation valuations may be achieved if the relationship between the agent in question and its recommending agent is considered. This is opposed to traditional techniques that assume that recommending agents are fully trusted. Ashri et al. (2005)[25] propose a method for dynamically identifying these relationships, categorizing them, and analysing them.

In this model, agents are defined as ‘entities described by a set of attributes’. Attributes are features of the environment, and agents are capable of performing actions by adding or removing these attributes. Agents also pursue goals, which are achieved by performing actions. Agent actions are divided into sensor capabilities, which retrieve the values of the environment's attributes, and actuator capabilities, which change the environment's attributes. Attributes that may be manipulated by an agent are defined as the agent's region of influence (RoI). Those that may be sensed by an agent are defined as the agent's viewable environment (VE). As a result, goals are divided into query goals that require an agent to perform a sensory action that lies within the agent's VE, and achievement goals that require an agent to perform an actuating action that lies within the agent's RoI. According to this model, relationships between agents may then be identified by studying how their VEs and RoIs overlap.

Relationships may then be characterized into several types, depending on the context. The relationship types illustrated by Ashri et al. (2005) lie in the context of an e-commerce scenario. First, two agents are said to be in a trade relationship if the goal of agent ‘a’ is to sell a product that agent ‘b’ may or may not wish to acquire. Second, one agent may be dependent on another, for instance, if agent ‘a’ is selling a product that agent ‘b’ wishes to buy. The intensity of the relationship depends on several factors, such as the number of sellers, the abundancy of the product, etc. This intensity basically determines who is dependent on whom and to what extent is it dependent on the other. In this case, the goal of the depending agent lies in the other agent's RoI; moreover, the other agent's RoI lies in the intersection of both agents' VEs. Third, two agents may be in a competitive relationship, for instance, if both are selling the same products. Again, the intensity of this relationship may depend on several factors, such as the price of the product, the market share, etc. In this case, either the agents share goals that lie in the intersection of their VEs, or they share RoIs that lie in the intersection of their VEs. Fourth, two agents may be in a collaborative relationship, for instance, if agent ‘a’ is selling goods to agent ‘b’ while ‘b’ is also selling goods to ‘a’. This is a combination of two trade dependency relationships. In this case, the goals of ‘b’ lie within the RoI of ‘a’, the goals of ‘a’ lie within the RoI of ‘b’, and the RoIs of both ‘a’ and ‘b’ lie in the intersection of their VEs. Finally, relationships between more than two agents may be considered. The resulting configuration would be composed of the four configurations presented above. However, some exceptions may arise giving special privilege to one agent over the other.

Computing trust and reputation may now be modified to accommodate the additional information obtained from identifying relationships. Sample rules are provided. For example, in the case of having a dependency relationship between two peers, the initial trust value is set to an arbitrary low value (in other words, confidence is low) if the intensity of the relationship is high, while it is set to a high value if the intensity is low.


Revyu and del.icio.us Tag Analysis for Finding the Most Trusted Peer

The main goal of Heath et al. (2007)[26] is to find out who knows what and who is the most trustworthy in delivering information on a specific subject. To achieve this, topic experience profiles are generated for each peer using ‘Revyu’, ‘del.icio.us’, and FOAF descriptions.

Previous empirical studies showed that people usually based their trust on the following five factors: expertise, experience, affinity, impartiality, and track record. The different factors were selected based on the criticality of the task and subjectivity of possible solutions. However, the first three were given much more emphasis than the others. Hence, the research of Heath et al. (2007) focused on computing the affinity factor when the trust relationship is between two individuals, and the expertise and experience factors when the trust relationship is between an individual and a certain topic.

To compute the expertise (or credibility) factor, Revyu tags are inspected. For each tag, all items tagged with that tag are obtained. Then for each item, the mean item rating is obtained and each review of the item is inspected. At the end, each reviewer will have its credibility score updated.

To compute the experience (or usage) factor, Revyu tags and user tags on del.icio.us are inspected. The algorithm counts how many times has each reviewer reviewed an item tagged with that tag. At the end, each reviewer will have its tag counts (or usage score) updated.

Note that both algorithms above have one crucial problem: if the user is the only reviewer then this reviewer will obtain credibility and usage scores of 1!

Finally, the affinity between two individuals is computed based on the analysis of their reviews in Revyu and some further basic user details from FOAF. The algorithm looks for the items that both reviewers have reviewed. An ‘item overlap ratio’ is obtained by dividing the number of items reviewed by both peers by the highest number of reviews by either peers. Then, the ‘mean rating overlap’ is obtained by taking into consideration the average rating distance of both reviewers (the difference in their ratings of each common item they have reviewed). However, how the item overlap ratio is combined with the mean rating distance to obtain the affinity factor has no clear answer yet, although two possible options are provided.


A NodeRank Algorithm for Computing Reputation

The basic goal of Pujol et al. (2002)[27] is to use a ranking algorithm to establish the reputation of nodes in a social network. The idea is that properties about a person's degree of expertise (or his reputation) may be inferred from how well this person is connected in his social network.

Pujol et al. (2002) build their social networks using information from personal web pages, reports or documents authorship, participation in a project, hierarchical structure in the community or organization, sharing of physical resources, sharing of virtual resources (e.g. news groups, forums, etc.), and email traffic.

A NodeRanking algorithm is proposed for creating a ranking of reputation ratings. The idea is that the ranking of a node would rely on its ‘degree of authority’, or what may be seen as the degree of ‘importance’ of the node. “Authority of a node ‘a’ is calculated as a function of the total measure of authority present in the network and the authority of the nodes pointing to node ‘a’.”

Note that this method requires no user feedback and is similar to Pagerank. However, while Pagerank uses global information of the network graph, NodeRank uses only local information.


Propagation of Trust in Social Networks

Golbeck and Hendler (2006)[28] focus on three properties of trust: transitivity, asymmetry, and personalization. Transitivity implies that trust may be passed between people. For example, if our trusted friend trusts a certain plumber, then we might take our friend's trust into consideration and decide that we will also trust the plumber. However, trust is not strictly transitive. In other words, it is not always the case that if Alice trusts Bob, and Bob trusts Chuck, then Alice should trust Chuck. Asymmetry implies trust is not necessarily reciprocal. In other words, if Alice trusts Bob, then this does not necessarily imply that Bob trusts Alice as well. Finally, personalization implies that trust is 'inherently a personal opinon'. In other words, given the trust values of each node in a social network, calculating the trustworthiness of the node in question will have different results when different peers are performing this calculation.

In this model, nodes label their neighbours as either trusted or not, using the binary values {0,1}. When questioning the trust of a given peer, the peer will poll its trusted neighbours only. When the neighbours reply, the peer will average their results and round the final value to obtain a binary value {0,1}. Each of the neighbours uses the same algorithm in obtaining their trust value of the peer in question. A variant of this model only rounds the value at the final step when the initial requester receives all results. This is called the non-rounding algorithm, while the first is called the rounding algorithm. Results show that the rounding algorithm outperforms the non-rounding one. This is because rounding intermediate results increases accuracy by removing more error.


Searching Social Networks via Referrals

Yu and Singh (2003)[29] focus on using referrals for searching dynamic social networks. However, no social network analysis has been used in the peer selection process. The authors argue that because building and maintaining a peer's social network is not feasible, distributed search through referrals is more promising.

In a referral system, peers send queries to other peers of the selected contacts. A response can either be an answer or another referral, allowing referrals to propagate in the social network. But how do peers select which peers to send their query to? To achieve that, each peer maintains a profile for itself and an acquaintance model for each of its acquaintances, modelled via the vector space model (VSM). Similarly, a query is modelled as a term vector. The similarity between a query and expertise of a given peer is defined as the cosine of the angle between them. This similarity measure is then used by a peer to help it select other peers to query. In addition to the similarity measure, a peer also considers the sociability of others (or their ability to give good referrals).

Weighted referral graphs are used to help the peer decide which querying peer to follow first. When another referral is received, the peer might decide to pursue it, even if the referred peer is not in its acquaintance list. This is how acquaintances are added. But if an answer is received, the peer updates its acquaintances by assigning rewards and penalties. Both the expertise and sociability vectors of the peer who sent the reply will be updated according to well defined functions.

Note that peers are assumed to be trustworthy is answering queries. For instance it is assumed that a peer answers a query only if it is confident of its expertise, or it may send back another referral only if it is confident in the relevance of the peer being referred.


Reciprocity as a Supplement to Trust and Reputation

An interesting overview to the 'evolution of cooperation' is provided by Mui (2002)[30]. In the context of LiquidPub, these theories may be used for defining the various incentives for peers to cooperate or defect (such as lying when rating others or providing unreliable reviews). Four theories are presented by Mui (2002): the group selection theory, the kinship theory, the reciprocation theory, and the social learning theory.

The group selection theory states that cooperation amongst individuals is not consistent with Darwin's theory. As an alternative, it suggests that cooperation is a result of natural selection being based on the group level: species, community, etc. However, strife is often observed within species. This weakens the group theory, suggesting the need for alternative theories.

The kinship theory states that individuals are ready to cooperate and sacrifice themselves for their kins, e.g. parents and children. The closer the relationship with the kin, the more altruism and less aggression is shown, even if it was over one's own personal benefits. However, the main problem with this theory is that it does not answer the relatedness and competition that sometimes exist among kins.

The reciprocation theory states that 'reciprocal altruism' is the reason behind individuals sacrificing their personal gain for the good of others. As such, all cooperative behaviours are viewed as postponing immediate personal gain to benefit from future reciprocations by others. Well defined equations are presented for computing reciprocation. Furthermore, this is the only theory (amongst the presented four) that has been verified by experimental work, proving that 'image scoring does play a role in actual human cooperation'.

Finally, the theory of social learning suggests that in the absence of kinship and reciprocation, cooperation is based on 'cultural transmission'. This implies that individuals learn the most dominant behaviour in their community. However, no experimental work has either proved or disproved this theory.

As for the computational trust model, Mui (2002) introduces the concept of reciprocity into its proposed computational model. While trust is defined as 'a subjective expectation an agent has about another's future behaviour' and reputation as the 'perception that an agent has of another's intentions and norms', reciprocity is defined as the 'mutual exchange of deeds, such as favour or revenge'. The relation between these three concepts is defined. In short, increasing reputations results in increasing trust, increasing trust results in increasing reciprocity, and increasing reciprocity results in increasing reputation. Similarly, decreasing any of these three values results in the reverse effect.

Information-Based Reputation

Sierra and Debenham (2009)[31] illustrates how reputation may be computed by aggregating peer opinions. The proposed method makes use of social network analysis to decide how opinions may be aggregated when there is some sort of dependence between opinions.

The basic idea is that a peer may express its opinion about a given aspect of the object being analysed in a given context. The opinion is described as a probability distribution over an evaluation space 'E'. After forming an opinion, an agent may then share this opinion with the rest of the group. A group discussion then takes place, after which the agent may or may not revise their opinions, based on how much can others convince them about changing their opinion. Finally, the group as a whole tries to reach a unified group opinion. Reputation is then defined as the "social evaluation by the group".

Of course, sharing opinions is the central point of this paper. The idea is that shared opinions affect the future opinions of other peers. Hence, Sierra and Debenham (2009) [31] proposes a simple and basic communication model for sharing opinions. Opinions then influence each other based on the "semantic similarity" between the two concepts being evaluated.

Forming opinions is affected by several measures, such as the time decay factor, the reliability of the information source, etc. The accuracy of an agent's opinion may sometime be verifiable within a reasonable amount of time. For example, if one gives their opinion about the weather tomorrow, then this opinion may be verified the next day by actually observing the weather and comparing it to what the agent predicted. However, not all opinions may be verified, such as the opinion about the quality of a given scientific paper. In such cases, the opinion may then be evaluated by comparing it to the group opinion.

Three different methods are then proposed for the aggregation of opinions, in the hope of reaching one final group opinion. The dependent method aggregates the opinions of agents that have been discussing/sharing their opinions together. If this method fails to return results, then the data is deemed inconsistent and the agents should have further discussions or agree to disagree. Otherwise, the Y-method proposed the group opinion with maximum certainty. If this result is rejected by the agents, then the final proposal is to say that the group opinion lies some where between the result computed by the dependent method and that of the independent method, which assumes that the priors are completely independent.

Social network analysis is used to help analyse the dependence between two opinions. For example, in the case of scientific publications, this dependence may be a measure of co-authorship or affiliation. Also, social network analysis may be used to calculate the initial confidence of an agent's opinion. This confidence is the direct result of the agent's expertise in the area it is giving an opinion on. Again, in the field of scientific publications, the expertise may be calculated based on how many highly cited papers is the agent an author of, how many prestigious papers did it review, whether it has a central role in the college, etc.


References

  1. ↑ Ramchurn, S. D., Huynh, T. D., and Jennings, N. R. (2004). Trust in Multiagent Systems. The Knowledge Engineering Review, 19 (1), pp. 1-25.
  2. ↑ Castelfranchi, C. and Falcone, R. (2000). Trust is Much More than Subjective Probability: Mental Components and Sources of Trust. Proceedings of the 33rd Hawaii International Conference on System Sciences (on-line edition).
  3. ↑ Brainov, S. and Sandholm, T. (1999). Contracting with Uncertain Level of Trust. Proceedings of the First ACM Conference on Electronic Commerce, pp. 15-21.
  4. ↑ Sabater, J., Sierra, C. (2005) Review on computational trust and reputation models. Artificial Intelligence Review 24, pp. 33–60
  5. ↑ Ramchurn, S., Hunyh, D., Jennings, N. (2004) Trust in multi-agent systems. The Knowledge Engineering Review 1 pp. 1—25
  6. ↑ J. Sabater, C. Sierra (2001) Regret: a reputation model for gregarious societies, in: Proceedings of the Fourth Workshop on Deception, Fraud and Trust in Agent Societies, Montreal, Canada pp. 61–69.
  7. ↑ Sabater, J., Paolucci, M., Conte, R. (2006) Repage: Reputation and image among limited autonomous partners. Journal of Artificial Societies and Social Simulation 9(2)
  8. ↑ Sierra, C., Debenham, J. (2005) An information-based model for trust. In: Proceedings of the fourth international joint conference on autonomous agents and multiagent systems (AAMAS-05), Utrecht, Netherlands. pp. 497—504
  9. ↑ Carbo, J., Molina, J., Davila, J. (2002) Trust management through fuzzy reputation. Int. Journal in Cooperative Information Systems 12 pp. 35—155
  10. ↑ Huynh, T. D., Jennings, N. R. and Shadbolt, N. (2004) FIRE: an integrated trust and reputation model for open multi-agent systems. In: 16th European Conference on Artificial Intelligence, Valencia, Spain
  11. ↑ 11.0 11.1 eBay: http://www.eBay.com
  12. ↑ 12.0 12.1 Amazon Auctions: http://auctions.amazon.com
  13. ↑ 13.0 13.1 Zacharia, G. (1999) Collaborative Reputation Mechanisms for Online Communities’. Master’s thesis, Massachusetts Institute of Technology
  14. ↑ 14.0 14.1 A. Altman, M. Tennenholtz (2005) Ranking Systems: The PageRank Axioms, in Proceedings of the 6th ACM conference on Electronic commerce (EC-05), Vancouver, Canada pp. 1 - 8
  15. ↑ 15.0 15.1 J. Kleinberg (1998) Authoritative sources in a hyperlinked environment. In Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, ACM Press, New York pp. 668-677
  16. ↑ Gyöngyi, H. Garcia-Molina, J. Pedersen (2004) Combating Web Spam with TrustRank. Proceedings of the International Conference on Very Large Data Bases 30:576
  17. ↑ OnSale: http://www.onsale.com
  18. ↑ 18.0 18.1 Dellarocas, C. (2003) The digitalization of Word-Of-Mouth: Promise and Challenges of Online Reputation Mechanisms. Management Science
  19. ↑ Glickman, M. E. (1999) Parameter estimation in large dynamic paired comparison experiments. Applied Statistics (48), pp. 377—394
  20. ↑ 20.0 20.1 Newman, M. E. J. (2003). The Structure and Function of Complex Networks. SIAM Review, pp. 167-256.
  21. ↑ Kleinberg, J. M. (2000). Navigation in a Small World. Nature, pp. 845-845.
  22. ↑ Newman, M. E. J. (2001). Who is the Best Connected Scientist? A Study of Scientific Coauthorship Networks. Physical Review E, 64:016132.
  23. ↑ Chirita, P. A. , Damian, A., Nejdl, W., and Siberski, W. (2005). Search Strategies for Scientific Collaboration Networks. Proceedings of the 2005 ACM workshop on Information Retrieval in Peer-to-Peer Networks, pp. 33-40.
  24. ↑ Sabater, J. and Sierra, C. (2002). Reputation and Social Network Analysis in MultiAgent Systems. Proceedings of First International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 475-482.
  25. ↑ Ashri, R., Ramchurn, S. D., Sabater, J., Luck, M., and Jennings, N. R. (2005). Trust Evaluation Through Relationship Analysis. Proceedings of Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1005-1011.
  26. ↑ Heath, T., Motta, E., and Petre, M. (2007). Computing Word-of-Mouth Trust Relationships in Social Networks from Semantic Web and Web2.0 Data Sources. Workshop on Bridging the Gap between Semantic Web and Web 2.0 at 4th European Semantic Web Conference, Innsbruck, Austria.
  27. ↑ Pujol, J.M., Sangüesa, R., and Delgado, J. (2002). Extracting Reputation in Multi Agent System by means of Social Network Topology. Proceedings of the First International Joint Conference on Autonomous Agents and Multi-Agent Systems, 1, pp. 467-474. Bologna, Italy.
  28. ↑ Golbeck, J. and Hendler, J. (2006). Inferring Trust Relationships in Web-based Social Networks. ACM Transactions on Internet Technology, pp. 497-529.
  29. ↑ Yu, B. and Singh, M. (2003). Searching Social Networks. Proceedings of Second International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 65-72.
  30. ↑ Mui, L. (2002). Computational Models of Trust and Reputation: Agents, Evolutionary Games, and Social Networks. PhD thesis at MIT.
  31. ↑ 31.0 31.1 Sierra, C. and Debenham, J. (2009). Information-Based Reputation. PhD thesis at MIT.
Retrieved from "http://wiki.liquidpub.org/mediawiki/index.php/State_Of_The_Art/Trust_Reputation_And_Social_Network_Analysis"
Personal tools