This thesis investigates both theoretical and practical aspects of the design
and analysis of iterative algorithms for trust and reputation management and recommender
systems. It also studies the application of iterative trust and reputation
management mechanisms in ad-hoc networks and P2P systems.
First, an algebraic and iterative trust and reputation management scheme (ITRM)
is proposed. The proposed ITRM can be applied to centralized schemes, in which a
central authority collects the reports and forms the reputations of the service providers
(sellers) as well as report/rating trustworthiness of the (service) consumers (buyers).
It is shown that ITRM is robust in filtering out the peers who provide unreliable
ratings. Next, the first application of Belief Propagation algorithm, a fully iterative
probabilistic algorithm, on trust and reputation management (BP-ITRM) is
proposed. In BP-ITRM, the reputation management problem is formulated as an
inference problem, and it is described as computing marginal likelihood distributions
from complicated global functions of many variables. However, it is observed that
computing the marginal probability functions is computationally prohibitive for large
scale reputation systems. Therefore, the belief propagation algorithm is utilized to
efficiently (in linear complexity) compute these marginal probability distributions. In
BP-ITRM, the reputation system is modeled by using a factor graph and reputation
values of the service providers (sellers) are computed by iterative probabilistic message
passing between the factor and variable nodes on the graph. It is shown that
BP-ITRM is reliable in filtering out malicious/unreliable reports. It is proven that
BP-ITRM iteratively reduces the error in the reputation values of service providers
due to the malicious raters with a high probability. Further, comparison of BP-ITRM with some well-known and commonly used reputation management techniques (e.g.,
Averaging Scheme, Bayesian Approach and Cluster Filtering) indicates the superiority
of the proposed scheme both in terms of robustness against attacks and efficiency.
The introduction of the belief propagation and iterative message passing methods
onto trust and reputation management has opened up several research directions.
Thus, next, the first application of the belief propagation algorithm in the design of
recommender systems (BPRS) is proposed. In BPRS, recommendations (predicted
ratings) for each active user are iteratively computed by probabilistic message passing
between variable and factor nodes in a factor graph. It is shown that as opposed to
the previous recommender algorithms, BPRS does not require solving the recommendation
problem for all users if it wishes to update the recommendations for only a
single active user using the most recent data (ratings). Further, BPRS computes the
recommendations for each user with linear complexity, without requiring a training
period while it remains comparable to the state of art methods such as Correlationbased
neighborhood model (CorNgbr) and Singular Value Decomposition (SVD) in
terms of rating and precision accuracy.
This work also explores fundamental research problems related to application of
iterative and probabilistic reputation management systems in various fields (such as
ad-hoc networks and P2P systems). A distributed malicious node detection mechanism
is proposed for delay tolerant networks (DTNs) using ITRM which enables every
node to evaluate other nodes based on their past behavior, without requiring a central
authority. Further, for the first time. the belief propagation algorithm is utilized in
the design and evaluation of distributed trust and reputation management systems
for P2P networks. Several schemes are extensively simulated and are compared to
demonstrate the effectiveness of the iterative algorithms and belief propagation on
these applications. |