Trust Management for the Semantic Web Matthew Richardson1 Rakesh Agrawal2 Pedro Domingos By Tyrone Cadenhead Overview The semantic web is a large uncensored system to which anyone may contribute Raises question of how much credence to give to each source Tackle by employing concept of web of trust in which each user maintains trusts in a graph of a small number of other users Compose these trusts into trust values for all users Each user receives a personalized set of trusts Overview Anyone can be an information producer or consumer of anyone else s information Major issue of how to decide the trustworthiness of each information source Sheer magnitude and diversity of sources make it impossible to have all information be consistent and of high quality Model One solution is to establish the degree of belief in a statement that is explicitly asserted by one or more sources on the semantic web User s belief in a statement should be a function of her trust in the sources providing it bi f j tij Authors propose solution based on recursive propagation of trust If A has trust u in B and B has trust v in C then A should have some trust t in C that is a function of u and v S users R trust aRb by transitive closure Model Beliefs any user i may assert her personal belief bi in the statement in the range 0 1 The collection of personal beliefs in a statement is a column vector b Trusts user i may specify a personal trust tij for any user j Trust is in range 0 1 tij may be different from tji The collection of personal trusts is a NxN matrix T Merging we want to compute for any user their belief in a statement given by Merged beliefs The trust between any two users is given by the merged trust matrix Matrix T Vector b T t1 1 t1 2 t1 3 t1 4 t1 5 b 1 t2 1 t2 2 t2 3 t2 4 t2 5 2 t3 1 3 t4 1 4 T5 1 t5 2 T5 3 T5 4 T5 5 5 Algorithm 1 Path Algebra Interpretation Assumption that a merged belief depends only on the paths of trust between the user and any other user with a personal belief in the statement Algorithm Enumerate all paths between the user and every user with a personal belief in the statement Calculate the belief associated with each path by applying a concatenation function to the trusts along the path and also the personal belief held by the final node Combine those beliefs with an aggregation function Path Algebra Interpretation Let represent the concatenation function and represent the aggregation function E g tik tkj is the amount that user i trusts user j via k If is addition and is multiplication then k tik tkj tiktkj Matrix operation C A B such that Cij k Aik Bkj Local Belief Merging Let well formed decomposable path problems be defined for which is commutative and associative and is associative and distributive over Algorithm In step 2 the user needs only the merged beliefs of her immediate neighbors which allows her to merge beliefs locally Definitions Let be addition and be multiplication Commutative a b b a Associative a b c a b c Associative a b c a b c Distributive a b c a b a c Cycles It is improbable a web of trust will be acyclic A combination function is cycle indifferent if it is not affected by introducing a cycle in the path between two users With cycle indifference the aggregation over infinite paths will converge since only the finite number of paths without cycles affect its calculation Algorithm 2 Probabilistic Interpretation Imagine a random knowledge surfer hopping from user to user in search of beliefs At each step the surfer probabilistically selects a neighbor to jump to according to the current user s distribution of trusts With probability equal the current user s belief the random surfer says yes I belief in the statement Otherwise it says No When choosing which user to jump to the random surfer will with probability i 0 1 ignore the trusts and instead jump directly to the original user i Probabilistic Interpretation is the probability that at any given step user i s random surfer is at user j i is the probability that at any given step user i s random surfer says yes I belief in the statement This is based on random walks on a Markov chain The convergence properties of such random walks are well studied and will converge as long as the network is irreducible and aperiodic ij Computation User i s trust in user j is the probability that her random surfer is on a user k times the probability that the surfer would transition to user j summed over all k And is the probability that user i s random surfer says yes This is the probability that the random surfer is on a given user times that user s belief in the statement Cont d User i selects a neighbor probabilistically according to her distribution Ti and then with probability 1 accepts the neighbor s merged belief and with probability accepts her own belief In Matrix form is This says that a user may compute her merged trusts knowing only the merged trusts of her neighbors Definitions Aperiodic there exists an integer k 1 that divides all cycles Irreducible graph remains unchanged after a reduction algorithm is applied Idempotent multiple applications of the operation does not change the result x x x Transitive Closure given set S binary relation R aRb S set of humans R parent of transitive closure of R is aRb means a is the ancestor of b
View Full Document
Unlocking...