# Social Recommendation Based on Quantified Trust and User's Primary Preference Space
## 4 User Trust Quantification Based on Random Walk with Restart (TQ_RWR)  
The random walk method was originally used to calculate the quality ranking of different web pages [28]. In this paper, user nodes are considered as analogs of web pages, and whether users trust each other is analogous to the jump between web pages. First, a binary adjacency matrix \(T\) of the user trust network is constructed, where each element \(T_{ij}=1\) indicates that user \(u_{i}\) trusts user \(u_{j}\), and \(T_{ij}=0\) indicates that user \(u_{i}\) does not trust user \(u_{j}\). Due to the asymmetry of the trust relationship, the adjacency matrix \(T\) is an asymmetric matrix. In order to represent the jump probability between different user nodes, the matrix \(T\) is transposed and normalized by column to obtain a state transition matrix \(T^{\prime}\), where each element \(T^{\prime}_{ij}\) represents the probability of user \(u_{j}\) trusting user \(u_{i}\)  
Figure 1: User trust network. Figure 2: Social scene and shopping scene. After a personalized random walk, we will obtain an credibility vector. A high credibility rating implies that a user is reliable, with others putting a high level of trust in him or her. We establish a credibility vector \(r^{k}=[r_{1}^{k},r_{2}^{k},\ldots,r_{N}^{k}]^{T}\) which indicates the credibility rank and the stationary visiting probability of each users after the \(k\)th random walk. Moreover, the vector \(r\) is defined as the solution of the following equation:  
\[r^{k+1}=T^{\prime}\times r^{k}. \tag{1}\]  
The equation above shows the process of random walk. \(u_{j}\); \(k\) and \(k+1\) indicate the times of random walk. The initial value of vector \(r\) is defined as \(r^{0}=[1/N,1/N,\ldots,1/N]^{T}\) which indicates that each user is elected with equal probability when starting to random walk. In the user trust network, there are many user nodes similar to node \(B\) and node \(D\) in Figure 3. The node similar to \(B\), with only in-degree and no out-degree, is called a termination node, and the node similar to node \(D\) with a self-loop is called a trap [29]. In the state transition matrix \(T^{\prime}\), all elements of the column corresponding to the terminating node \(B\) are 0. After multiple random walks, all elements of the credibility vector \(r\) are 0. If there is a trap in the trust network, the main diagonal of the state transition matrix has at least one element equal to 1. There will be \(n\) ones on the main diagonal to represent \(n\) traps in the entire network. When walked to the trap, it will not jump to other nodes forever. Moreover, the element representing the trap in the trust vector \(r\) is 1, and other elements are 0. No matter whether there is a termination node or a trap, we cannot use Equation (1) to random walk to obtain an accurate credibility vector \(r\). Hence, we also cannot quantify the trust between users. In order to solve the problem of termination nodes and traps in the trust network, we use the method named random walk restart (RWR) to calculate the credibility vector \(r\). When the current state of random walk is a termination code or a trap, it randomly jumps to the initial node with a certain probability to restart. The process of RWR is expressed as:  
\[r^{k+1}=p\times T^{\prime}\times r^{k}+(1-p)\times r^{0}. \tag{2}\]  
where \(p\) represents the probability of continuing to walk from the current user node, and \((1-p)\) represents the probability of jumping from the current node to the initial user node to restart the random walk. The size of \(p\) is inversely proportional to the convergence speed of the iteration for Equation (2). The convergence speed will be slow and affect the performance of the method if \(p\) is too large. Otherwise, it will not reflect the effect of the walk [30]. We let \(p=0.80\). After a certain number iteration, the credibility vector \(r\) converges [31]. The larger entry \(r_{j}\) of vector \(r\) is, the higher credibility of the user \(j\) is, and the higher trust formed by other users on the user \(j\).