In order for us to produce the metrics we require we need to understand the various types and models of trust and algorithms available.

Global Trust

Global trust is a measure of the reputation of users based on their dealings with the network as a whole. It is not user specific, i.e. the value a user has is the same value regardless of which user is assessing it. A simple measure of global trust would be a mean of the ratings supplied to a given user, but this is only a measure of local trust activity and is open to abuse. A more robust system would need to take account of information from the whole network, looking at how trustworthy the suppliers of the ratings are.

One algorithm that achieves this is EigenTrust, which was was originally designed to address the issue of inauthentic or malicious files in peer-to-peer file sharing networks. The authors however note many of the characteristics of trust also apply to social networks and they discuss e-Bay’s reputation systems as a model for calculating local trust values. EigenTrust works in a manner similar to Google’s page rank algorithm. Local, direct trust values are assigned to peers and then normalised to a value between 0 and 1 and these are then weighted by the reputations of the assigning peers and aggregated to produce a global reputation[1].

Global trust (reputation) is easier to compute, and useful as a measure of how trustworthy a group of users is – it can be used to assess specific areas of a social network. It is however not context specific and does not take into account the needs, risks and circumstances of an individual user. For this we need to be able to look at trust along specific paths within the network.

Provenance Based Trust

A based level of trust in a user can be established using background information from their use of  established social media platforms to provide an initial baseline trust level. More details about this can be seen here

Path Based Trust

In this post I define path based trust as that which is assessed along a path between two nodes. Path based trust is context specific, i.e. the value will depend on which node is assessing it. This metric is useful for a user in specific interactions with another user, when the context is needed to asses the level of risk.

Direct Trust

This is between two nodes which have interacted and have existing trust relationships based on their experience of each other.

• Direct behavioural trust based on interactions between nodes (users), i.e. average rating rating given for each interaction.
• Direct content trust based on the average ratings given to posts by the user

Indirect Trust

Indirect trust is a product of the transitive/propagative feature of trust. i.e.
A→ trusts → B → trusts → C , therefore A→ trusts → C,
so A has an indirect trust relationship with C. This is complicated by the fact that trust is not strictly transitive; A → trusts → C, but not necessarily to the same extent that B does. The extent to which A → trusts → C depends on the extent to which A → trusts → B. It will also be affected by other paths between A and C. Because of this we say that trust is propagative rather than transitive. Trust is not a binary condition that can be inferred along a path, but rather a quality that can be passed along. Trust relationships are also directional and irreflexive: t(A,B) != t(B,A).

To calculate indirect trust metrics then, we need to turn to graph theory and the characteristics of network topology to calculate trust along a path between users. There is a sizeable body of work looking at network trust and several algorithms have been devised. These all use a social network modelled as a directed graph with the nodes representing social network users, edges representing a trust relationship between them and edge labels representing the trust value of the edge. The following algorithms calculate trusts between two indirectly connected nodes by looking at the edges that make the path between them.

TidalTrust [2] calculates trust by focusing on at the shortest paths between nodes, because of findings by the Authors that network proximity produces more accurate results. In even a moderately sized network there will be more than one shortest path, so the algorithm calculates the trust between two nodes on paths of the shortest length via the trustor nodes most trusted neighbour and works recursively along that path to calculate the trust metric. This algorithm gives inaccurate results if there is a unique shortest path and these are magnified if it is a long path with low trust values. It also does not make full use of all the information in the network graph [2] .

RN-Trust [3] takes a novel approach by viewing the edges in a path as resisters in a circuit. Resistance is calculated from local trust values and then calculated along a path in much the same way as electrical resistance is calculated along a circuit of series resistors. Multiple path can be accounted for with calculations for parallel resistors. This gets over the single path problems in TidalTrust but suffers for the reverse problem of considering too much information in the network. Because there is no threshold to dictate whether a path is useful or whether its trust value is too weak to be useful [2]. This algorithm is also likely to be computationally costly.

SWTrust [4] uses breadth first search to find trust paths between two nodes. The algorithm uses a parameter to limit the length of path considered. The average trust values are multiplied by the average value of the edges between the trustee’s immediate neighbours. This algorithm considers all nodes in the graph on paths shorter that the specified value and so will look at malicious nodes making it vulnerable to ‘gaming’. The average of a wide range of values between 0 and 1 means there are very few extreme values so the results are less useful for users making decisions.

TISoN [2] is an algorithm that has been designed to address all of the issues mentioned above. It does not consider all paths between the nodes in question and instead make use of the TPS algorithm for searching for optimal paths along which to compute trust. The TPS algorithm is parameterised with values for time to live (ttl) and minimum trust threshold (mtt). The paths are searched for from the source (trustor) node which checks its neighbours for a trust value for the destination (|trustee). If one is not found the node is added to the path, the ttl value is decremented and the algorithm checks the new node’s neighbours for a trust value to the destination and so on until either the ttl reaches 0, n which case the path is rejected, or the destination is found in which case the path is accepted. The mtt value is use to check the trust relation between each node in the path; if the trust value does not exceed mtt the path is also rejected.

Once the TPS algorithm has run the set of optimal paths is the used to compute the inferred trust value. First a propagative algorithm is used to calculate the strength of each path. The strength of the relationship is computed along each path to the direct neighour of the trustee. This avoids bias caused by the trustee’s neighbours and reflects the confidence of the wider network in the trust value. The algorithm considers the average direct trust value of edges along the path, the variance and the path weight, which is the fraction relationship between path length and that of the shortest path in the set.

The aggregate trust score from the path that has the highest trust value is then selected as the most trusted path and used to generate the trust rating between the nodes. This algorithm has the advantage of being highly configurable. The values for mtt and ttl can effect the computational cost and accuracy of the final trust score. The accuracy will also effect the usefulness of the score and so very accurate scores will have less extreme values in many cases, especially well connected nodes in large networks. These decisions are all configurable by both the user and the social network provider.

This algorithm has performed very well in tests and seems well suited. It allows for the generation of context specific trust metrics between users where the providing application and user can very the inputs to the algorithm depending on the level of risk posed by the interaction.

The Trust Machine Strategy

In the trust machine application a network graph can be created by mapping nodes to users in its client applications. This graph is stored in the trust machine and we will use it to calculate trust for all clients, so one user in our network may map to users belonging to the same individual in client applications. There will be two categories of user, anonymous users, who have not authenticated via established providers such as Facebook, twitter and eBay and those who have, who will be able to generate a certain amount of trust from their behaviour, connectedness and lack of anonymity.

The generation of a reputation metric using the EigenTrust algorithm combined with user provenance will give us a base level of trust. We can then generate useful trust scores between individuals using an implementation of the TISoN algorithm. This will interact with the base level reputation to give a useful rating of a user and their fitness to do business. There are clearly going to be several factors that affect the calculations for each user which are going to pose quite a challenge, especially as some calculations of trust between users will need to be done at runtime in order to provide up to date responses to API calls. This will require some skilful and carefully conceived coding, not just in implementing the algorithms, but in designing the classes to supply them on the fly and doing so in a robust and maintainable manner. More of which in another post…

References

[1] S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina, ‘The eigentrust algorithm for reputation management in p2p networks’, in Proceedings of the 12th international conference on World Wide Web, 2003, pp. 640–651.

[2] S. Hamdi, A. L. Gancarski, A. Bouzeghoub, and S. B. Yahia, ‘TISoN: Trust Inference in Trust-Oriented Social Networks’, ACM Trans. Inf. Syst., vol. 34, no. 3, pp. 1–32, Apr. 2016.

[3] M. Taherian, M. Amini, and R. Jalili, ‘Trust Inference in Web-Based Social Networks Using Resistive Networks’, 2008, pp. 233–238.

[4] W. Jiang and G. Wang, ‘SWTrust: Generating Trusted Graph for Trust Evaluation in Online Social Networks’, 2011, pp. 320–327.