Alternate trust metric algorithm

Raph Levien
1 Apr 2002

The Attack Resistant Trust Metric Metadata HOWTO contains a simple algorithm for computing a trust metric. This page contains an alternate algorithm, which may be more efficient in some cases. As far as I can tell, it will produce very similar or identical results. Intuitively, the main algorithm flows data backwards along trust edges, while this one (like PageRank) flows it forwards.

The algorithm

Let R[i,j] be the confidence that user i has in assertion j.

In the "step", we compute a new R'[i,j] based on the old R[i,j], the trust graph, and the assertions local to the users i. Initialze R'[i,j] to all zeros.

For each user i:

Find the predecessors of i (ie, the users who have issued a peer certificate for i).

Add the vector R[i] to each R'[p] for each predecessor p of i. Store as new R'[p].

For each user i:

Multiply the vector R'[i] by the damping factor (0.85) divided i's outdegree (if the outdegree is zero, use zero). Store as new R'[i].

For each assertion j:

If i has a local assertion matching j, set R'[i,j] to 1 if it's an exact match, or 0 if it just matches the template for the assertion (ie if the assertion is inconsistent with j).
Again, optionally, divide each R'[i,j] by the sum over j of R'[i,j] (if zero, use zero).
Now, copy R'[i,j] to R[i,j] for all i, j.

Free software