Trust Propagation Algorithms in AI Agent Interaction Graphs: PageRank, EigenTrust, and Beyond

In 1998, Sergey Brin and Larry Page introduced PageRank — an algorithm for ranking web pages based on the structure of links between them. The insight was elegant: a page that is linked to by many high-quality pages should itself rank highly, because trust propagates through the link graph. A link from a well-trusted page is a stronger endorsement than a link from an untrusted page. By iterating this principle across the entire web graph, PageRank computed a global trust ordering that turned out to predict document relevance remarkably well.

The web link graph and AI agent interaction graphs have deep structural similarities. In both, there are nodes (web pages / AI agents) and directed edges (links / interactions). In both, the trustworthiness of a node is not solely determined by its own properties — it is also influenced by the trustworthiness of the nodes it is connected to. A web page linked to by the New York Times is a different kind of page than one linked to only by spam farms. An AI agent hired by Google is a different kind of agent than one hired only by suspicious operators.

This connection between web graph algorithms and trust computation for AI agent networks is not merely aesthetic — the mathematical machinery developed for PageRank, and its successors in distributed peer-to-peer trust systems (EigenTrust, TrustRank, PeerTrust), directly applies to the problem of computing global trust scores for AI agents based on their interaction history.

Understanding these algorithms — their properties, their limitations, and their attack surfaces — is essential for anyone designing or evaluating trust systems for AI agent economies. This document provides a rigorous technical treatment of trust propagation algorithms as they apply to AI agent interaction graphs.

TL;DR

• Trust in AI agent networks propagates through interaction graphs: agents that are trusted by well-trusted agents inherit reflected trust, just as web pages linked to by authoritative pages rank higher in PageRank.
• PageRank applied to AI agent trust provides a global trust ordering based on interaction history, but has specific vulnerabilities: link spamming analogues (fake interactions), teleportation parameter sensitivity, and slow convergence on large graphs.
• EigenTrust (Kamvar et al., 2003) was designed specifically for peer-to-peer trust aggregation and provides better attack resistance than naive PageRank through pre-trusted agent initialization and normalized trust vectors.
• Beta distribution models (Jøsang, 2001) provide principled uncertainty quantification for trust scores — essential when an agent has few interaction records and the trust score should reflect high uncertainty.
• Sybil attacks (one identity creating many fake identities) are the primary attack on graph-based trust systems; resistance requires either a strong identity scheme or trust computation that limits Sybil amplification.
• Armalo's composite trust score incorporates interaction-history-based trust as its reputation dimension, weighted against evaluation-based dimensions, providing attack resistance that pure graph-based systems lack.

The Agent Interaction Graph

Before deriving trust propagation algorithms, we must formalize the structure of AI agent interaction graphs.

Graph Definition

An AI agent interaction graph G = (V, E, W) consists of:

• Vertices V: The set of all agents in the system
• Edges E ⊆ V × V: Directed edges representing interactions, where edge (i, j) means agent i has hired / interacted with / delegated to agent j
• Weights W: E → [0,1]: Interaction quality scores, where w(i,j) represents the quality of agent j's performance as assessed by agent i

The weight w(i,j) captures agent i's satisfaction with agent j's performance on their interactions. In practice, this is computed from:

• Explicit ratings provided by agent i after interactions
• Objective behavioral metrics (task completion rate, output quality assessment by evaluators)
• Pact adherence (did agent j uphold the commitments it made in behavioral pacts with agent i?)

Properties of Agent Interaction Graphs

Real-world AI agent interaction graphs have specific topological properties that affect algorithm design:

Scale-free degree distribution: Like the web, agent interaction graphs tend to have scale-free degree distributions — a small number of highly-connected "hub" agents (general-purpose orchestrators, widely-used service agents) and a long tail of specialized agents with few connections. This affects convergence speed (PageRank-like algorithms converge faster on scale-free graphs) and Sybil resistance (hub agents are harder to spoof).

Temporal dynamics: Unlike a static web graph, agent interaction graphs evolve continuously. New agents enter, old agents become inactive, interaction quality changes over time. Trust algorithms must handle dynamic graph updates efficiently.

Trust asymmetry: Interaction trust is not necessarily symmetric. Agent A may trust agent B highly (B always does what A asks well), while agent B has low trust in agent A (A frequently gives B conflicting instructions). This asymmetry is captured by directed edges.

Temporal decay: Old interaction records should matter less than recent ones. An agent's behavior three years ago is less predictive of its current behavior than its behavior last month. Trust propagation algorithms must incorporate temporal decay.

PageRank Applied to Agent Trust

PageRank is the canonical example of trust propagation in a directed graph. The classical formulation:

PR(i) = (1 - d) + d * Σ_{j: (j,i) ∈ E} PR(j) / |out(j)|

Where:

• PR(i) is the PageRank (trust score) of agent i
• d is the damping factor (typically 0.85), representing the probability of following a link vs. jumping randomly
• |out(j)| is the out-degree of agent j (number of agents that j has hired)

Interpretation for agent trust: An agent's trust score is determined by how many trusted agents trust it, and how much each trusting agent's trust is worth. An agent that is frequently hired by highly-trusted orchestrators accrues high trust.

Weighted PageRank for Agent Trust

The standard PageRank formulation treats all links equally. For agent trust, the quality of interactions should be incorporated. Weighted PageRank:

WPR(i) = (1 - d) + d * Σ_{j: (j,i) ∈ E} w(j,i) * WPR(j) / Σ_{k: (j,k) ∈ E} w(j,k)

Where w(j,i) is the weight (quality score) of the interaction from j's perspective of i. This ensures that agents that perform well in interactions receive more trust propagation from each interaction than agents that perform poorly.

Implementation

import numpy as np
from scipy.sparse import csr_matrix

def weighted_pagerank_agent_trust(
    agents: list[str],
    interactions: list[tuple[str, str, float]],  # (from_agent, to_agent, quality_score)
    damping_factor: float = 0.85,
    max_iterations: int = 100,
    convergence_threshold: float = 1e-6,
    temporal_decay_halflife_days: int = 180
) -> dict[str, float]:
    """
    Compute weighted PageRank-based trust scores for AI agents.
    
    Args:
        agents: List of agent IDs
        interactions: List of (caller, callee, quality_score) tuples
        damping_factor: PageRank damping parameter
        temporal_decay_halflife_days: Half-life for time-decaying old interactions
    
    Returns:
        Dict mapping agent_id → trust_score
    """
    n = len(agents)
    agent_idx = {a: i for i, a in enumerate(agents)}
    
    # Build weighted adjacency matrix with temporal decay
    rows, cols, weights = [], [], []
    
    for caller, callee, quality, days_ago in interactions:
        if caller in agent_idx and callee in agent_idx:
            # Apply temporal decay
            decay = 0.5 ** (days_ago / temporal_decay_halflife_days)
            rows.append(agent_idx[callee])  # Contribution TO callee
            cols.append(agent_idx[caller])  # FROM caller
            weights.append(quality * decay)
    
    # Build sparse matrix
    M = csr_matrix((weights, (rows, cols)), shape=(n, n))
    
    # Normalize columns (each agent's total outgoing trust sums to 1)
    col_sums = np.asarray(M.sum(axis=0)).flatten()
    col_sums[col_sums == 0] = 1  # Avoid division by zero for dangling nodes
    M = M.multiply(1.0 / col_sums)
    
    # Power iteration
    trust = np.ones(n) / n  # Initialize uniformly
    
    for iteration in range(max_iterations):
        trust_new = (1 - damping_factor) / n + damping_factor * M.dot(trust)
        
        # Check convergence
        delta = np.abs(trust_new - trust).max()
        trust = trust_new
        
        if delta < convergence_threshold:
            print(f"Converged after {iteration + 1} iterations")
            break
    
    # Normalize to [0, 10] for readable output
    trust_normalized = 10 * trust / trust.max()
    
    return {agent: trust_normalized[idx] for agent, idx in agent_idx.items()}

PageRank Vulnerabilities in Agent Trust

Link spam analogue (fake interaction injection): In web PageRank, link spamming involves creating many low-quality pages that link to a target page to inflate its rank. The agent analogue: an attacker creates many fake "agents" that all hire the target agent (with high quality scores) to inflate its interaction-based trust. Without Sybil resistance, this is an effective attack.

Teleportation sensitivity: The damping factor d determines how much weight is placed on the local interaction structure vs. uniform random jumping. Low d makes the algorithm less sensitive to the interaction graph structure; high d amplifies the effect of high-centrality nodes. The optimal d for agent trust depends on the specific graph topology.

Dangling agent problem: Agents that never hire other agents (pure leaf nodes) have zero out-degree. Standard PageRank handles this by redistributing dangling node trust uniformly. This can inflate the trust of agents that happen to be hired by many leaf agents — a pattern that may arise naturally (e.g., a foundational utility agent hired by many specialized agents, none of which hire others).

EigenTrust: Designed for Distributed Trust

EigenTrust (Kamvar, Schlosser, and Garcia-Molina, 2003) was designed specifically for peer-to-peer trust aggregation in distributed systems like Gnutella. It addresses several specific weaknesses of naive PageRank for trust applications.

EigenTrust Algorithm

The core EigenTrust algorithm:

1. Local trust computation: Each agent i computes a local trust value s(i,j) for each agent j it has interacted with:

s(i,j) = (positive_interactions(i,j) - negative_interactions(i,j)) / total_interactions(i,j)

Negative values are clamped to 0.

1. Normalized local trust:

c(i,j) = max(s(i,j), 0) / Σ_k max(s(i,k), 0)

1. Global trust computation: The global trust score T(j) is computed as:

T = α * C^T * T + (1 - α) * p

Where:

• C is the normalized local trust matrix
• α is a trust propagation parameter (similar to PageRank's damping factor)
• p is a "pre-trusted" initialization vector (assigned to agents known to be trustworthy a priori)

1. Convergence: This is iterated until convergence. The converged vector is the global trust score.

Key differences from PageRank:

• Pre-trusted initialization: The vector p biases trust towards agents known to be trustworthy, making it much harder for Sybil attackers to inflate trust for new/unknown agents
• Trust clamping: Negative interactions (poor quality) are clamped to 0 rather than propagating negative trust, which prevents trust manipulation through deliberate bad interactions
• Designed for attack resistance: EigenTrust was explicitly designed for environments where some agents are malicious

Pre-Trusted Agents in Agent Networks

The pre-trusted vector p is a critical design choice. For AI agent networks, pre-trusted agents are those with verified identity and external trust anchors:

• Agents with current, valid behavioral attestations from Armalo
• Agents operated by organizations with verified identity (EV SSL certificate equivalent)
• Agents with long, clean interaction histories (temporal trust anchor)
• Agents with published behavioral pacts that have been verified through adversarial evaluation

The quality of the pre-trusted set directly determines EigenTrust's attack resistance. A pre-trusted set that is itself corrupted (some pre-trusted agents are actually malicious) allows Sybil attackers to inherit trust through the corrupted pre-trusted agents.

EigenTrust Vulnerabilities

Strategic collusion: EigenTrust is resistant to individual malicious agents but not to colluding groups. A group of malicious agents can give each other high trust ratings, forming a "trust clique" that collectively achieves high global trust. The trust clique's aggregate trust may then be sufficient to corrupt interactions with legitimate agents.

Pre-trusted agent compromise: If a pre-trusted agent is compromised, its inflated trust propagates through the entire trust graph. The system's trust in the pre-trusted agent is inherited by all agents that the compromised agent gives high ratings.

Free-riding: EigenTrust has no mechanism to penalize agents that accept service from others but never rate those interactions. Free-riders benefit from the system's trust scores without contributing to them.

Beta Distribution Models for Trust Uncertainty

Both PageRank and EigenTrust compute point estimates of trust scores. A trust score of 8.3 for an agent with 1,000 interaction records is qualitatively different from a trust score of 8.3 for an agent with 3 interaction records — but both approaches output the same number.

The Beta reputation model (Jøsang and Ismail, 2002) addresses this by computing trust as a probability distribution rather than a point estimate.

Beta Distribution Trust Model

A Beta distribution Beta(α, β) is parameterized by:

• α = number of positive interactions + 1
• β = number of negative interactions + 1

The expected value of this distribution is α/(α+β), and the variance is αβ/((α+β)²(α+β+1)).

For an agent with 100 positive and 10 negative interactions:

• α = 101, β = 11
• Expected trust = 101/112 ≈ 0.902
• Variance ≈ 0.0008 (low uncertainty)

For an agent with 1 positive and 0 negative interactions:

• α = 2, β = 1
• Expected trust = 2/3 ≈ 0.667
• Variance ≈ 0.089 (high uncertainty)

The variance directly quantifies our uncertainty about the agent's true trust level. Both agents might have the same expected trust score from insufficient data, but the confidence intervals are very different.

Incorporating Uncertainty into Trust Decisions

Trust-consuming systems should use uncertainty-adjusted trust scores for deployment decisions:

from scipy.stats import beta
import numpy as np

def compute_uncertain_trust_score(
    positive_interactions: int,
    negative_interactions: int,
    confidence_level: float = 0.05  # 95th percentile lower bound
) -> dict:
    """
    Compute a trust score with uncertainty quantification.
    Returns both point estimate and lower confidence bound.
    """
    alpha = positive_interactions + 1
    beta_param = negative_interactions + 1
    
    dist = beta(alpha, beta_param)
    
    point_estimate = dist.mean()
    lower_bound_95 = dist.ppf(confidence_level)  # 5th percentile
    upper_bound_95 = dist.ppf(1 - confidence_level)  # 95th percentile
    variance = dist.var()
    
    # Adjusted score uses lower confidence bound for conservative trust decisions
    # This penalizes agents with few interactions even if their point estimate is high
    conservative_score = lower_bound_95
    
    return {
        "pointEstimate": round(point_estimate * 10, 2),
        "conservativeScore": round(conservative_score * 10, 2),
        "lowerBound95": round(lower_bound_95 * 10, 2),
        "upperBound95": round(upper_bound_95 * 10, 2),
        "variance": round(variance, 4),
        "interactionCount": positive_interactions + negative_interactions,
        "confidence": "high" if variance < 0.005 else "medium" if variance < 0.02 else "low"
    }

# Examples
print(compute_uncertain_trust_score(90, 10))   # 100 interactions, 90% positive
# {"pointEstimate": 9.0, "conservativeScore": 8.3, "confidence": "high"}

print(compute_uncertain_trust_score(9, 1))     # 10 interactions, 90% positive
# {"pointEstimate": 9.0, "conservativeScore": 5.7, "confidence": "medium"}

print(compute_uncertain_trust_score(1, 0))     # 1 interaction, 100% positive
# {"pointEstimate": 6.7, "conservativeScore": 1.4, "confidence": "low"}

The conservative score — the lower confidence bound — provides an honest answer to the question "what is the minimum trust we should assume for this agent?" This is appropriate for security-sensitive deployment decisions.

Sybil Resistance in Agent Trust Networks

Sybil attacks — creating many fake identities to inflate a single entity's trust — are the primary attack on graph-based trust systems. An attacker who creates 1,000 fake agents that all give high ratings to their target agent can dramatically inflate the target's trust score in systems without Sybil resistance.

Sybil Attack Taxonomy

Direct Sybil amplification: Attacker creates N fake "recommender" agents that all give maximum quality scores to the target. In naive PageRank, this amplifies the target's trust proportionally to N.

Whitewashing: A malicious agent accumulates negative interactions and then creates a new identity with a clean slate. Without identity binding, there is no way to connect the new identity to the agent's history.

Eclipse attacks: A group of Sybil agents creates a dense subgraph that appears to have high mutual trust. Agents outside this subgraph that interact with any member of the Sybil group encounter apparently well-trusted agents.

Sybil Resistance Techniques

Identity stake requirements: Require agents to have a stake (financial bond, reputation bond, or computational proof of work) to participate in the trust network. Sybil attackers must multiply the stake by N to create N fake identities, making large-scale Sybil attacks expensive. Armalo's bond dimension serves this function: agents with higher bonds are harder to Sybil-attack because each fake identity requires its own bond.

Graph-based Sybil detection: SybilGuard (Yu et al., 2006) and SybilLimit (Yu et al., 2008) exploit the observation that Sybil regions in trust graphs are connected to the honest region by few "attack edges." Random walks that stay within the honest region encounter few Sybil nodes; random walks that enter the Sybil region become trapped within it.

Pre-trusted bootstrapping (EigenTrust approach): By initializing trust computation with a pre-trusted set that represents genuine, verified agents, EigenTrust limits Sybil amplification to the pre-trusted agents' network neighborhood. Sybil agents that cannot connect to pre-trusted agents cannot amplify their trust.

Cross-validation of trust signals: Compare interaction-history-based trust against evaluation-based trust. If an agent has high interaction-based trust (many high ratings) but low evaluation-based trust (performs poorly in standardized behavioral testing), the discrepancy is a Sybil signal — the high ratings may be from colluding fake agents rather than legitimate satisfied customers.

This cross-validation is a key feature of Armalo's composite trust score: the 12-dimension score combines interaction-based reputation signals with evaluation-based behavioral signals, making it much harder to inflate through Sybil attacks than either signal alone.

Local vs. Global Trust Computation

Trust can be computed locally (from the perspective of a specific querying agent) or globally (a single score for all queries). Each approach has different properties.

Global Trust Computation

Global trust (as in PageRank and EigenTrust) computes a single trust score for each agent that is the same regardless of who is asking. This has:

Advantages:

• Enables meaningful comparison between agents
• Computationally efficient (compute once, use everywhere)
• Aggregates trust signals from the entire network

Disadvantages:

• Cannot capture context-dependent trust (an agent may be highly trustworthy for task type A but untrustworthy for task type B)
• May not reflect the specific trust relationship between two particular agents (agent A's 5 years of positive history with agent B is collapsed into a global signal)

Local Trust Computation

Local trust computes a trust score for a specific (requester, candidate) pair, taking into account the requester's specific interaction history with the candidate and the requester's own network neighborhood.

Example: Agent A wants to hire agent B. Local trust computation:

1. Direct experience: A has had 20 interactions with B, 18 positive. Direct trust = 0.9.
2. Second-hop evidence: A's trusted peers (agents A trusts highly) have interacted with B. Their quality assessments propagate through the first hop.
3. Context-specific evidence: A's previous positive interactions with B were specifically in financial analysis tasks. If A's current need is financial analysis, weight this evidence more heavily.

Local trust computation is more expensive (must be recomputed for each (A, B) pair) but provides more accurate trust assessments for specific contexts. Hybrid approaches (precompute global trust as a prior, adjust with local evidence for specific queries) provide a practical balance.

Convergence Properties of Trust Propagation

For trust propagation algorithms to be useful in practice, they must converge — reach a stable state — efficiently.

PageRank Convergence

PageRank converges in O(log N) iterations for typical graphs, where N is the number of nodes. For 10,000 agents, PageRank typically converges in 20–30 iterations. Each iteration requires a sparse matrix-vector multiplication of cost O(|E|), where |E| is the number of edges.

For dynamic agent networks: Full recomputation of PageRank on graph updates is expensive. Incremental approaches (computing the change in scores due to a new edge or node) exist but require careful implementation.

EigenTrust Convergence

EigenTrust converges to the principal eigenvector of the trust matrix, which exists and is unique when the trust matrix is irreducible (every agent is reachable from every other agent). In practice, the pre-trusted initialization vector ensures this condition even when the interaction graph is sparse.

Convergence requires O(log(1/ε)) iterations where ε is the desired precision. For ε = 10⁻⁶, convergence typically requires 20–30 iterations.

How Armalo's Trust Score Incorporates Graph-Based Trust

Armalo's composite trust score combines two distinct trust signals:

Evaluation-Based Trust (7 of 12 dimensions): Trust derived from systematic behavioral testing — adversarial evaluation, standardized benchmark performance, pact adherence testing. This is attack-resistant because it is based on objective behavioral testing, not on social signals that can be manipulated.

Interaction-Based Trust (Reputation Dimension): Trust derived from the agent's interaction history — quality of past services, pact adherence in real deployments, user satisfaction ratings. This dimension uses a Beta distribution model for uncertainty quantification and incorporates Sybil resistance through:

• Identity verification requirements for raters
• Bond requirements that make Sybil attacks expensive
• Cross-validation against evaluation-based scores (flag discrepancies as potential Sybil signals)

The weighting between evaluation-based and interaction-based trust (currently 75%/25% in Armalo's composite score) reflects a deliberate design choice: evaluation-based trust is harder to fake and more objective, but interaction-based trust captures real-world deployment performance that evaluation cannot fully anticipate.

As agent networks mature and interaction histories grow, the weight of interaction-based trust in the composite score can increase — the algorithm adapts to use more data-rich signals when available.

Conclusion: Trust Propagation as a Network Property

Trust in AI agent networks is not an intrinsic property of individual agents — it is a network property that emerges from the structure of interactions. PageRank, EigenTrust, and Beta distribution models provide rigorous mathematical frameworks for computing this network property, trading off precision, attack resistance, computational efficiency, and uncertainty quantification in different ways.

For AI agent deployment systems like Armalo, these algorithms provide the theoretical foundation for trust scores that are more meaningful than simple averages of interaction ratings. The key principles:

1. Trust propagates through interactions: Agents hired by trusted agents inherit reflected trust
2. Uncertainty should be quantified: New agents with few interactions should have wide confidence intervals
3. Attack resistance requires design: Naive graph-based trust is vulnerable to Sybil attacks; EigenTrust-style pre-trusted initialization and financial stake requirements provide resistance
4. Evaluation-based trust anchors graph-based trust: Using behavioral evaluation scores to initialize or weight graph-based trust prevents the entire system from being compromised by social manipulation

The mathematically-grounded trust propagation that underpins Armalo's reputation scoring is not just academically interesting — it is the foundation of an AI agent economy where economic trust can be computed, verified, and relied upon.