Abstract—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.

Index Terms—trustworthy networks, trust transitivity, measurement of transitive trustworthiness, max-min trust degree, max-mean trust degree, NP-hardness  

Cite: Yixiang Chen, Tian-Ming Bu, Min Zhang, and Hong Zhu, "Measurement of Trust Transitivity in Trustworthy Networks," Journal of Emerging Technologies in Web Intelligence, Vol. 2, No. 4, pp. 319-325, November 2010. doi:10.4304/jetwi.2.4.319-325