# User Trust Inference in Online Social Networks: A Message Passing Perspective
## 3 The Proposed Model
### Model Construction
#### 3.2.3 Model Formulation  
The random variables in our model are the states or labels of corresponding nodes. For a user node, its state is a predefined measurement for the user from the original online social network. It can be direct statistics of this user or carefully handcrafted measurement calculated from information obtained from their OSN data. For demonstration purpose and brevity, we use user categories defined by the online social service as user node states in this paper. For a trustRelation node, which represents the trust relationship between the trustor user and the trustee user, the random variable's state is the trust relationship's existence in the OSN dataset. As each node has a state, each edge has a state-state pair (or a transition state) that is determined by the states of the two nodes connected by it. Table 6 summarizes state configurations used in this paper. Due to the way that we model trust relationships as random variable nodes in the probabilistic graph, the smallest significant structure in the resulting graph is pairwise. (Although there will be smallest cliques that consist of three trustRelation nodes if the second category of auxiliary features is leveraged, we still model the conditional random field and run probabilistic inference on it pairwisely.) Different pairwise structures are connected via the common user nodes or trustRelation nodes. It is worth noting that each node, if connected by a dummy node, can also be viewed as a pairwise structure, and thus we call each node a unitary structure. Each unitary structure has a set of associated _node feature functions_ and each pairwise structure has a set of _edge feature functions_. In our problem setting, we attach features to each node and edge. The features used in this paper are the user profile features, UGC features, and trust propagation features. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Type** & **States** & **Description** \\ \hline \hline Node & & \\ \hline \hline user (u) & 0, 1, 2 & User categories defined by the OSN. \\ \hline \hline trustRelation (t) & 0 & Such an relationship is observed. \\ \cline{2-3}  & 1 & Such an relationship is un-observed. \\ \hline \hline Edge (U: state of user node, T: state of trustRelation node) \\ \hline \hline \multirow{2}{*}{\(\text{E}_{u\leftrightarrow t}\)} & UT: \(00,01\), \(10,11,20,21\) & state–state pair consisting of U and T. \\ \hline \multirow{2}{*}{\(\text{E}_{t\leftrightarrow u}\)} & TU: \(00,01\), \(02,10,11,12\) & state–state pair consisting of T and U. \\ \hline \multirow{2}{*}{\(\text{E}_{t\leftrightarrow t^{\prime}}\)} & TT: \(00,01,10,11\) & state–state pair consisting of T and T. \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Configurations of node state and edge state–state pair. We use T and T\({}^{*}\) to denote the set of all known trust relationships and the set of trust links whose states are unknown, respectively. Let \(\Psi\) denote the set of feature weights, and the proposed model that computes a conditional distribution can be defined as  
\[P(\mathrm{T}^{*}|\mathrm{U},\mathrm{T};\Psi)=\frac{1}{Z(\mathrm{U},\mathrm{T})} \prod_{i}\varphi_{i}(\mathrm{U},\mathrm{T};\Psi), \tag{4}\]  
where \(Z(\cdot)\) is the normalization constant, and \(\varphi_{i}\) is the \(i_{\mathrm{th}}\) potential function for either a unitary structure or a pairwise structure. For any node \(\mathrm{V}_{i}\in(\mathrm{U},\mathrm{T},\mathrm{T}^{*})\) or any edge \(\mathrm{E}_{j:\langle\mathrm{V}_{s},\mathrm{V}_{i}\rangle}\) connecting nodes \(\mathrm{V}_{s}\) and \(\mathrm{V}_{t}\), the potential functions for either unitary structures or pairwise structures used in this paper are, respectively, defined in the log-linear form as follows.