# User Trust Inference in Online Social Networks: A Message Passing Perspective
## 3 The Proposed Model
### Model Construction  
Many modern online social services have deployed a feature which allows their users to build friend networks. It is common understanding that trust has a dedicated role in forming friendships between two individuals, and thus many trust-related studies also use friend networks in OSNs as trust networks. In particular, there are several online services that have explicitly implemented trust networks as web of trust--such online services include Epinion ([[http://www.epinions.com/](http://www.epinions.com/)]([http://www.epinions.com/](http://www.epinions.com/)) (accessed on 28 February 2018)) and Ciao ([[http://www.ciao.co.uk/](http://www.ciao.co.uk/)]([http://www.ciao.co.uk/](http://www.ciao.co.uk/)) (accessed on 19 June 2021)).  
We modeled our learning and inference tasks through a conditional random field (CRF), one of probabilistic graphical model variations. The structure of the probabilistic graphical model was built upon the trust network of an OSN, and the features that were to be added to the model were extracted and then built from the UGC data from the OSN. Due to the way that the UGC and topological features are embedded into the trust network, the CRF model not only uses both the explicit trust information (the trust network) and the user-generated contents from the social network, but also has the capability of capturing the interplay among various types of features extracted from the UGC and the network topology.  
Differently from the conventional link prediction problem in which edges between nodes represent trust relationships, our method represents relationships as nodes. In other words, we model a real-world directional trust link as a trust relationship node in the model.  
Figure 1: Two primary trust propagation strategies. (**a**) Direct trust propagation. (**b**) Transposed trust propagation.  
Therefore, the random variables in the CRF model are the predefined states or labels of users and trust relationships. (In this paper, we use \"state\" and \"label\" interchangeably.) In the CRF model, the two types of random variable nodes in the probabilistic graph are:  
* **user** node. It can be either a _trustor_ node or a _trustee_ node;
* **trustRelation** node. It represents an observable or a nonexistent trust link in the network.  
Figure 2 demonstrates the difference between a trust relationship commonly represented in real social networks and one modeled by our approach.  
For a user-user pair whose trust relationship is un-observed in the OSN, the objective of the model in this paper is to infer the probabilities of labels of the corresponding _trustRelation_ node whose state is unknown in the probabilistic graph, so that the trust relationship can be predicted.  
It is worth looking at how we handle edges in the model. Edges in a CRF are usually homogeneous in type. That means edges in the graph do not have to be type-specific. However, without breaking any conventional rule for model inference, we may particularly mark edges with dedicated types so that different edges can delegate different types of meanings and thus serve different purposes. In our model, the type of an edge between a _trustor_ node and a _trustRelation_ node is different from the type of an edge between a _trustRelation_ node and a _trustee_ node. It is also worth noting that involving different edge types grant the model the possibility of recognizing directional trust between a pair of two users. An example of modeling the mutual relationship between two users is demonstrated in Figure 3.  
Figure 3: A demonstration of modeling two users’ mutual relationship in the proposed model.  
Figure 2: Demonstration of one user trusting another in the real world and in the proposed model. (**a**) Real-world trust relationship representation: user\({}_{\text{A}}\) trusts user\({}_{\text{B}}\). (**b**) user\({}_{\text{A}}\) trusting user\({}_{\text{B}}\) rendered in the proposed model.