Reputation Graph

Edges in a reputation graph are directed (A trusts B, not necessarily vice versa) and weighted to represent the strength of endorsement. This asymmetry is critical for modeling real-world trust, where a security researcher's endorsement of a code repository carries a different weight than a casual user's star. The weight can be a continuous value (0.0 to 1.0) or a discrete signal.

• Explicit Trust: A user directly vouches for another entity.
• Implicit Trust: Derived from actions like citing, linking, or transacting.
• Negative Edges: Advanced graphs may include distrust or flagging edges to combat Sybil attacks.

The core value of a graph structure is trust transitivity. If node A trusts node B, and node B trusts node C, the graph can compute a derived trust score for A → C. This is typically achieved through algorithms like EigenTrust or personalized PageRank, which propagate trust along edges in iterative matrix multiplication steps until scores converge.

• Attenuation: Trust decays with each hop to prevent infinite propagation.
• Convergence: Algorithms stop when score changes fall below a threshold (e.g., 10^-6).
• Seed Selection: Trusted seed nodes are often manually curated to prevent spam from hijacking the graph.

A reputation graph must be resilient against Sybil attacks, where a malicious actor creates thousands of fake nodes to artificially inflate their standing. The graph structure itself provides defense: fake nodes typically only receive edges from other fake nodes, forming a disconnected cluster that isolates them from the legitimate, well-connected core.

• Graph Partitioning: Algorithms detect dense subgraphs of mutually endorsing fake accounts.
• Entry Barriers: Requiring a proof-of-work or stake to add nodes increases attack cost.
• Trust Depth Limiting: Restricting propagation to a maximum hop count (e.g., 3-4 hops) limits the influence of distant, untrusted clusters.

Trust is not static. A reputation graph incorporates temporal dynamics by applying a decay function to edge weights based on the age of the endorsement. An endorsement from 10 years ago should carry less weight than one from last month. This ensures the graph reflects current behavior, not just historical glory.

• Exponential Decay: Weight = original_weight * e^(-λ * time_elapsed).
• Sliding Windows: Only endorsements within the last N days are considered active.
• Event-Driven Updates: A new negative event (e.g., a security breach) can trigger an immediate, sharp decay in incoming trust edges.

Before trust can be computed, the graph must solve the entity resolution problem: determining that @Alice on GitHub, Alice.com, and did:example:alice all refer to the same real-world entity. Without this, reputation fragments across disconnected nodes. Canonicalization merges these identities into a single, definitive node.

• Deterministic Matching: Using verified email domains or cryptographic public keys.
• Probabilistic Matching: Using machine learning on behavioral patterns and metadata.
• Decentralized Identifiers (DIDs): W3C-standard identifiers that are inherently unique and self-sovereign, simplifying resolution.

A reputation graph can compute two distinct types of scores. A global trust score represents the consensus of the entire network (e.g., EigenTrust). A subjective trust score is personalized, computed from the perspective of a specific node using only its local neighborhood (e.g., Personalized PageRank). Subjective views are critical because trust is inherently personal; a node you trust implicitly might be distrusted by the wider network.

• Subjective Logic: A mathematical framework for modeling belief, disbelief, and uncertainty in subjective trust.
• Web of Trust (PGP): A classic example where each user acts as their own root of trust.

A mechanism that reduces the weight of historical behavioral data over time, ensuring the reputation score reflects an entity's most recent performance. Without decay, a node that was trustworthy five years ago retains high scores even after turning malicious. Decay functions can be:

• Exponential: score halves at fixed intervals
• Linear: score decreases by a constant amount per time unit
• Event-driven: triggered by specific actions or inactivity