Abstract
A trust network is a social network in which edges represent the trust relationship between two nodes in the network. In a trust network, a fundamental question is how to assess and compute the bias and prestige of the nodes, where the bias of a node measures the trustworthiness of a node and the prestige of a node measures the importance of the node. The larger bias of a node implies the lower trustworthiness of the node, and the larger prestige of a node implies the higher importance of the node. In this paper, we define a vector-valued contractive function to characterize the bias vector which results in a rich family of bias measurements, and we propose a framework of algorithms for computing the bias and prestige of nodes in trust networks. Based on our framework, we develop four algorithms that can calculate the bias and prestige of nodes effectively and robustly. The time and space complexities of all our algorithms are linear w.r.t. the size of the graph, thus our algorithms are scalable to handle large datasets. We evaluate our algorithms using five real datasets. The experimental results demonstrate the effectiveness, robustness, and scalability of our algorithms.
Introduction
In modern social networks such as Epinions or Slashdot, interactions go beyond simple connections; they involve explicit expressions of trust and distrust. Analyzing these networks requires robust metrics to quantify two key attributes of nodes: prestige (the importance or perceived value of a node) and bias (the degree to which a node's ratings deviate from the consensus or "global truth").
Traditional ranking systems like PageRank and HITS are often inadequate for trust networks because they typically ignore negative edges (distrust) and do not account for the inherent bias of the rater. This paper introduces a mathematical framework that addresses these shortcomings by modeling bias through vector-valued contractive functions, ensuring both stability and accuracy in large-scale social graphs.
The Problem: The "Cancellation Trap"
The previous state-of-the-art method, the MB algorithm, suffered from a significant vulnerability known as the "cancellation trap." Because it calculated bias using relative differences, a malicious user could manipulate their score. By giving some users extremely high ratings and others extremely low ratings, the relative differences could cancel out, resulting in a deceptively low bias score. This allowed "spammers" to maintain high influence while providing unreliable data.
The Proposed Framework: Contractive Functions
The core innovation of this research is the definition of bias as a vector-valued contractive function. By applying fixed-point theory, the authors prove that if the function is contractive, the iterative process will always converge to a unique, stable solution for both bias and prestige.
Based on this framework, four specific algorithms were developed:
- $L_1$-AVG / $L_2$-AVG: These calculate bias as the average absolute ($L_1$) or squared ($L_2$) difference between a node’s ratings and the prestige of the recipients.
- $L_1$-MAX / $L_2$-MAX: These focus on the maximum difference, ensuring that even a single highly unreasonable rating significantly impacts a node's bias score.
These algorithms operate iteratively: they refine prestige based on the trustworthiness of raters (defined as $1 - \text{bias}$), then update bias scores based on the new prestige values, repeating until convergence.
Experimental Evaluation
The framework was tested on five real-world datasets, including Kaitiaki (a small trust network), Epinions (a large signed network with 131k nodes), and three versions of Slashdot (signed networks with approximately 80k nodes each).
Key Results
The experimental results highlight three major strengths of the proposed algorithms:
- Accuracy: In signed networks, the $L_2$-AVG variant improved the Area Under the Curve (AUC) for bias detection by up to 11% over the MB algorithm.
- Robustness: Unlike the MB algorithm, which fails as the number of malicious actors increases, the $L_1$ and $L_2$ variants maintain high performance even in the presence of many spammers.
- Scalability: All four algorithms exhibit linear time and space complexity ($O(m)$), allowing them to process massive datasets efficiently, typically converging in 5 to 15 iterations.
Conclusion
This paper provides a rigorous mathematical foundation for assessing trust in social networks. By replacing relative differences with absolute and squared distances within a contractive framework, the authors have created a suite of algorithms that are not only more accurate but also resilient to adversarial manipulation. Future work will explore extending this framework to dynamic, time-evolving networks and investigating additional contractive functions tailored to specific attack vectors.
Summary updated