OSNs are readily becoming a trending platform where people meet and keep in touch with family and friends. It is used by people who want to find others who share common passion and interests. Nowadays, even businesses and organizations are tapping into the world of OSNs to conduct their daily professional conversations and activities. On an online social network, interactions are very complex due to their inherent graphical structure and also because they may involve conversing with strangers, some of whom might have malicious intent. This coupled with the lack of real-life face-to-face interaction and understanding amongst the users makes the concept of trust and ‘trust evaluation’ very essential. Trust evaluation aids in forming an opinion about a person’s or product’s trustworthiness which can further help in providing better user experience and functionality. Its increasing popularity explains the interests of researchers in designing new and better models for trust evaluation which can help in decision making in diverse applications. One such method that we will discuss is Graph-Based Trust Evaluation under which the OSN is depicted as a social graph.


As mentioned above, the Online Social Network is represented via a graph, called a social graph. Users are referred to as nodes of the graph and the relationship or interaction between them is represented by an edge connecting them. In an OSN, nodes can have direct as well as indirect interaction or contact with other nodes. This illustrates how trust can be built in both a direct or indirect manner. Trust that is built due to direct contact is known as the first-hand trust, while on the other hand trust that is built through indirect contact, i.e., through recommendations from other nodes is known as second-hand trust. Trust is quantified in this model by assigning the edges or path between nodes are a weight value between 0 and 1, where 0 depicts ‘no trust’ and 1 depicts ‘full trust.’ These values may vaiy from model to model.

The nodes in the graph can have one of the three roles namely a source (or trustor), a target (or trustee), or a recommender (an intermediate node on a trusted path). The source and target can be in direct contact. In this case, they have a given trust value for the edge between them. On the other hand, if they are not in direct contact, the trust value or trusted path between them can be generated by iterative recommendations. This means that the nodes that lie on the different paths connecting them can recommend different values (on the basis of the influence and personality of the user) that may be further used by being added directly or in a weighted manner (Figure 5.4).

In Figure 5.4, s, u, v, and d are the nodes representing the users in the OSN graph, u and v are in direct contact with d and thus they have an idea about the trustworthiness of d. The node s is not in direct contact with d but is directly connected with nodes u and v, so s forms it is the opinion of d, through u and v. In this manner, several sequential and parallel paths can be merged or overlapped to build a trusted graph between s and d. This is called the process of iterative recommendations.

Examples of trusted graph

FIGURE 5.4 Examples of trusted graph.


Trust evaluation models for OSNs are categorized by how they deal with a trusted graph. Mainly, there are two approaches: the graph simplification- based approach and the graph analogy-based approach. Models in both these approaches are discussed below:

Graph Simplification-Based Approach

Under this approach, a trusted graph is broken into multiple paths which have disjoint nodes and edges. It involves the creation of a directed series- parallel graph from a trusted graph by using the different possible paths under the guidance of some pre-defined principles. Some models that come under this categoiy are listed below:

  • 1. TidalTrust: This model uses trusted paths to produce recommendations about the degree of trust a user can put on another user. It does so by exploring trusted paths in a breadth-fust search manner, beginning from the trustor and ending on the trustee. Tidal Trust uses exclusively the shortest most robust trusted paths. Trust from s to d (tsd) is calculated using a threshold that has been set for being trustful and is referred to as max. The neighbor j is considered trustful only if t is more significant than this tlireshold value (max). Calculations begin from the trustor, move towards the trustee, and then the final value of the trust is returned from the trustee to the trustor.
  • 2. MoleTrust: Tiust evaluation through this model is divided into two steps:

i. Users are sorted according to their least distances from the trustor after which, cycles are detected.

ii. Input is given which consists of a maximum depth of users from the trustor. The term maximum depth is not dependent on any specific user. Thus, the tiusted graph is now a directed acyclic graph (DAG) which has been reduced.

So according to the above steps this model initially computes the trust degree of nodes that are at a single step distance from the trustor, then two steps and similarly goes on further. So, in general, a node which is at a к-steps distance from the trustor needs only the nodes which are k-1 steps away to calculate its degree of tiust. This implies that a node’s details are used once. The weighted average (WA) of the trust of every incoming trustful neighbor towards the trustee is then taken to come to a final value.

  • 3. MeTrust: It uses tiusted paths having multi-dimensional evidence. Tiust evaluation is done at three layers which are the node layer, the path layer, and the graph layer. The node layer deals with multidimensional trust and each node can have varying weight values for each dimension. Similarly, the second layer, i.e., path layer controls the rate at which tiust decays during the combination. In the end, the graph layer simplifies trusted graphs using three algorithms: GraphReduce, GraphAdjust, and WeightedAverage. In this model, many conceivable scenarios and mutable settings can be selected flexibly.
  • 4. SWTrust: This model assumes that a small trusted graph is already in existence and uses information about active domains of nodes to compute the tiust value, which is much better than using explicit trust ratings. Neighbor set of a node is classified into three classes by the social distance from the trustor that are local neighbors, more extended ties, and most extended ties. Adding an adjustable width feature in breadth-first search, the next-hop neighbors from the above three given classes at each search step are chosen. This model focuses on exploring the objective and stable information about a node such as their domain for the computation of trust and uses small trusted graphs for large OSNs.

Challenges faced by the graph simplification approach include path length limitation and evidence availability. These crop up because this approach makes use of both the composable as well as propagative nature of trust. In a trusted path, propagation means that if Node 1 trusts Node 2, and Node 2 trusts Node 3, then Node 1 can derive trust towards Node 3. Fixing an accurate path length is a challenge that the property of propagation causes, because while on the one hand, smaller path length may cause fewer paths to be discovered, on the other hand, a longer path length may lead to inaccurate prediction. The primary challenge of combining available evidence is caused due to multiple trusted paths in the graph.

< Prev   CONTENTS   Source   Next >