# Network Location-Aware Service Recommendation with Random Walk in Cyber-Physical Systems
## 5 The Proposed Prediction Models
### The Proposed Random Walk Models
#### 5.3.1 The State Transition of Random Walk  
In the graph, a user is a node, and the direct similarity of two users is the weight of the edge. Based on that, we build the undirected graph \(G(V_{u},E)\) and use Markov chain to model the state transition of random walk. A toy example of the undirected graph is given in Figure 5. Let \(u_{0}\in V_{u}\) be the start node, and the initial state be \(X_{0}=u_{0}\), representing that the initial state of random walk is in node \(u_{0}\). The state transition process after \(k\) steps is \(X_{0}\to X_{1}\rightarrow\ldots\to X_{k-1}\to X_{k}\). The state of the \(k\)th step is only decided by the state of the \(k-1\)th step. Assume that the node, which the \(k-1\)th step is in, is user \(u\), and the node that the \(k\)th step is in is user \(v\). The transition probability from node \(u\) to node \(v\) is  
\[prob(u,v)=Pr(X_{k}=v|X_{k-1}=u) \tag{5}\]  
Figure 4: The procedure of user-based random walk model.  
Figure 5: The undirected graph of user similarity.  
Note that, the weight of the edge connecting node \(u\) and node \(v\) is computed by Equation (3), and following that, we define the transition probability from node \(u\) to node \(v\) as  
\[prob(u,v)=Pr(X_{k}=v|X_{k-1}=u)=\frac{sim(u,v)}{\sum\limits_{v^{\prime}\in adj(u )}sim(u,v^{\prime})} \tag{6}\]  
where \(adj(u)\) is the adjacent node set of user \(u\), \(sim(u,v)\) is the similarity of user \(u\) and user \(v\), and \(sim(u,v)\) is the similarity of user \(u\) and the adjacent user \(v_{0}\). A higher similarity means a larger transition probability.  
Since the network configurations of users that are in the same autonomous system are likely to be similar, we aim to increase the transition probability among these users to enhance the similarity computation. In detail, we propose a transition weight \(\omega\) by introducing the network location information. For two adjacent users \(u\) and \(v\), the corresponding weight \(\omega\) is computed with  
\[\omega(u,v)=\frac{sim(u,U)+sim(v,U)}{2} \tag{7}\]  
where \(sim(u,U)\) represents the similarity of QoS values of user \(u\) and the average QoS values in set \(U\). The set \(U\) contains a certain number of users, and is decided by the following rules.  
1. If user \(u\) and user \(v\) are in the same autonomous system, then the set \(U\) contains the users of the autonomous system.
2. If user \(u\) and user \(v\) are in the same country, but not the same autonomous system, then the set \(U\) contains the users of the country.
3. If user \(u\) and user \(v\) are not in the same country or autonomous system, then the set \(U\) contains all users.  
After the weight computation, the transition probability in Equation (6) is enhanced to  
\[prob(u,v)=\frac{\omega(u,v)\times sim(u,v)}{\sum\limits_{v^{\prime}\in adj(u)} \omega(u,v^{\prime})\times sim(u,v^{\prime})} \tag{8}\]  
Based on the transition probability of the adjacent users, we construct a transition probability matrix \(M(M\in\mathbb{R}^{m\times m})\).  
\[M=\left[\begin{array}{ccc}M_{11}&\ldots&M_{1m}\\ \vdots&\ddots&\vdots\\ M_{m1}&\ldots&M_{mm}\end{array}\right]\]  
where each entry \(M_{uv}\)\((1\leq u,v\leq m)\) represents the transition probability \(prob(u,v)\). We give a detailed example based on Figure 4. There are four users in Figure 4, and we compute the similarity between each pair of users, and construct the transition probability matrix as follows.  
\[\left[\begin{array}{cccc}0&\frac{2}{3}&\frac{1}{3}&0\\ \frac{4}{13}&0&\frac{6}{13}&\frac{3}{13}\\ \frac{1}{4}&\frac{3}{4}&0&0\\ 0&1&0&0\end{array}\right]\]