Measurement of trust transitivity in trustworthy networks

In this paper, we 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. We 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. We focus on the analysis of the complexity of computing both kinds of trust degrees. We show that measuring the max-min trust degree is polynomial, however, measuring the max-mean one is NP-hard. Then we propose a matrix-based method to compute the max-mean trust degree, which can be done polynomially, but may produce non-simple paths. Finally, we give a simple example of a trust reputation network to illustrate the matrix-based method.