Measurement of Trust Transitivity in Trustworthy Networks

In this paper, the authors abstract the trust network as a weighted digraph. A path from node A to node B represents a transitive trust relationship. Parallel paths between a source and a target are associated with parallel trusts respectively. They introduce two measurements for computing the derived trust degree from a source to a target: Maxmin trust degree and Max-mean trust degree. The Max operator formalizes the choice among parallel paths. The min and mean operators compute the transitive trust degree along a path. They focus on the analysis of the complexity of computing both kinds of trust degrees. They show that measuring the max-min trust degree is polynomial, however, measuring the max-mean one is NP-hard.