Trust Rank

Unlike standard PageRank, which uses a uniform teleportation vector, Trust Rank biases the random surfer to jump exclusively to a curated seed set of trusted pages. This mathematical intervention ensures that trust flows outward from known good nodes, preventing spam farms from accumulating illegitimate authority. The teleportation probability, typically set between 0.1 and 0.15, controls how quickly trust dissipates as the walker moves away from the seed set.

The algorithm's efficacy depends entirely on the quality of the initial seed set. Seeds are selected through inverse PageRank to identify nodes that would collect the most PageRank if the link graph were reversed, ensuring broad coverage of the web. These candidates are then manually vetted by human experts to confirm they are trustworthy, non-spam pages. A typical seed set comprises 200-500 hand-picked URLs from domains like .gov, .edu, and established authoritative sources.

Trust propagates transitively but decays with each hop away from the seed set. The trust score of a node is the probability that a random walk starting from a trusted seed lands on that node. Key properties:

• Directly linked pages inherit high trust
• Two hops away receive significantly diminished trust
• Spam clusters isolated from the seed set receive near-zero scores This decay function mathematically guarantees that link farms cannot artificially inflate their standing.

A critical derivative metric, spam mass quantifies the portion of a page's PageRank that comes from untrusted sources. It is calculated as:

• Spam Mass = (PageRank - TrustRank) / PageRank A page with high PageRank but low TrustRank has a spam mass approaching 1.0, indicating its authority is almost entirely derived from spammy neighborhoods. This metric enables precise identification of pages that exploit link manipulation.

Trust Rank operates with the same O(n + m) complexity as PageRank, where n is the number of nodes and m is the number of edges in the web graph. The algorithm requires:

• A single sparse matrix-vector multiplication per iteration
• Convergence typically within 50-100 iterations
• Memory footprint proportional to the graph size This linear scalability makes it feasible for web-scale graphs containing billions of pages.

While PageRank distributes authority democratically based on link structure alone, Trust Rank introduces a normative bias toward human-verified quality. Key distinctions:

• PageRank: Purely structural, vulnerable to link spam
• Trust Rank: Semi-supervised, resistant to adversarial manipulation
• PageRank treats all pages as initially equal
• Trust Rank assigns zero initial trust to all non-seed pages This fundamental difference makes Trust Rank a spam-detection algorithm rather than a general authority metric.

The foundational link-analysis algorithm developed by Larry Page and Sergey Brin that assigns a global importance score to nodes in a directed graph based on the quantity and quality of incoming links. Trust Rank extends this model by biasing the random walk to start from a manually vetted seed set of trusted pages rather than a uniform distribution.

• Original formula: PR(A) = (1-d) + d * Σ(PR(Ti)/C(Ti))
• Damping factor d typically set to 0.85
• Converges iteratively using power iteration method
• Serves as the mathematical substrate for all modern authority propagation algorithms

The critical manual curation process of identifying a small, incontrovertibly trustworthy set of nodes that serve as the origin points for trust propagation. The quality of the seed set directly determines Trust Rank's effectiveness at combating web spam.

• Seeds must be selected by human experts for irreproachable authority
• Typical seed set size: 200–500 nodes for web-scale graphs
• Inverse PageRank can be used to discover good seeds automatically
• Poor seed selection leads to topic drift and degraded spam detection
• Seeds should span diverse topics to avoid topical bias in trust propagation

The algorithmic mechanism by which trust flows from the seed set outward through the graph along directed edges. Trust attenuates with each hop, meaning a node's trust score is a function of its distance from trusted seeds and the trustworthiness of intermediate nodes.

• Trust decays exponentially with graph distance from seeds
• A node linked to by many high-trust nodes inherits high trust
• Trust splitting: a node's trust is divided among all its outbound links
• Enables identification of trustworthy nodes that are not directly connected to seeds
• Forms the transitive closure of the trust relationship

A differential analysis technique that quantifies the degree to which a page's PageRank is inflated by untrustworthy sources. Calculated by subtracting a node's Trust Rank from its standard PageRank, revealing the portion of authority attributable to spam.

• Formula: Spam Mass = PageRank − Trust Rank
• High spam mass indicates manipulation via link farms or bought links
• Enables precise identification of nodes that appear authoritative but lack genuine trust
• Used to tune spam detection thresholds in search engines
• Can be normalized as a ratio: Spam Mass / PageRank for cross-domain comparison

An inverse formulation that starts the random walk from a seed set of known spam pages rather than trusted pages. Nodes receiving high Anti-Trust Rank scores are likely to be spam or closely associated with spam neighborhoods.

• Complements Trust Rank by identifying the untrustworthy frontier
• Useful when spam seeds are easier to identify than trusted seeds
• Can be combined with Trust Rank for a two-sided trust assessment
• Particularly effective at detecting colluding spam rings
• Often used alongside Trust Rank in ensemble spam classifiers

An extension of Trust Rank that segments the seed set by topical category and computes separate trust scores for each topic domain. A node may be highly trusted for medical information but untrusted for financial advice.

• Uses classifiers like Open Directory Project (DMOZ) categories to partition seeds
• Produces a trust vector rather than a scalar score
• Prevents topic drift where a trusted news site's endorsement of a spam pharmacy page would propagate inappropriate trust
• Enables topic-sensitive authority queries in search systems
• Requires a topical taxonomy or ontology for seed partitioning