Trust Propagation

The foundational principle that if entity A trusts entity B, and entity B trusts entity C, then A should have a derived level of trust in C. This is the logical basis for all propagation algorithms. The degree of transitivity is rarely absolute; it is typically dampened by a discount factor (e.g., 0.85) that reduces trust by a fixed percentage at each hop. Without this dampening, trust would diffuse uniformly across the entire graph, making the metric useless for distinguishing high-authority nodes from random ones. The formula for a single transitive path is: Trust(A,C) = Trust(A,B) * Trust(B,C) * DampingFactor.

The specific algorithms used to propagate scores across a reputation graph. Common strategies include:

• Breadth-First Search (BFS): Propagates trust outward in concentric rings from a seed set of trusted nodes. Ideal for computing Trust Rank.
• Random Walk with Restart: A simulated surfer traverses the graph, with a fixed probability of teleporting back to the seed set. The stationary distribution of visits becomes the trust score.
• Belief Propagation: A message-passing algorithm used in Bayesian Trust Networks where nodes iteratively exchange belief states until convergence.

The critical process of manually curating a small, incontrovertibly trustworthy set of nodes from which propagation begins. The quality of the seed set directly determines the quality of all propagated scores—garbage in, garbage out. Seeds are typically high-authority domains (e.g., justice.gov, stanford.edu) or known-good digital signatures. The seed set must be:

• Invulnerable to manipulation: No entity can buy or game their way in.
• Topically diverse: Covering multiple domains prevents bias toward a single sector.
• Regularly audited: Seeds can degrade; periodic human review is required.

The mathematical mechanisms that prevent infinite propagation loops and ensure trust decays with distance. Key techniques include:

• Damping Factor (d): A constant (typically 0.85) multiplied at each propagation step. After 5 hops, the original trust signal is reduced to d^5.
• Convergence Threshold: Propagation halts when the change in trust scores between iterations falls below a defined epsilon (e.g., 1e-9).
• Hop-Limit Pruning: A hard cutoff that stops propagation after a maximum number of edges (e.g., 6 hops), based on the 'six degrees of separation' principle.

Not all connections are equal. Edge weighting assigns a coefficient to each relationship to modulate how much trust flows across it. A citation edge from a peer-reviewed paper carries more weight than a hyperlink edge from a blog comment. Weight types include:

• Explicit Endorsement: A direct vouch or digital signature (weight: 1.0).
• Contextual Citation: A reference within a scholarly or authoritative document (weight: 0.7).
• Co-occurrence: Two entities frequently mentioned together in trusted corpora (weight: 0.3).
• Hyperlink: A standard HTML link, highly susceptible to spam (weight: 0.1).

A sink node (or dangling node) is an entity that receives trust but has no outgoing edges to propagate it further. In a closed system, sink nodes absorb and destroy trust, causing score leakage. Mitigation strategies include:

• Teleportation: Sink nodes are assumed to connect uniformly back to all seed nodes, redistributing their accumulated trust.
• Dummy Edge Insertion: A low-weight edge is added from the sink to a universal 'super-sink' node that re-injects trust into the graph.
• Score Re-normalization: After each iteration, all scores are re-normalized to sum to 1.0, compensating for the lost mass.