# Network Location-Aware Service Recommendation with Random Walk in Cyber-Physical Systems
## 5 The Proposed Prediction Models
### The Proposed Random Walk Models
#### 5.3.2 The Transition Probability Matrix  
Let \(Pr(X_{k}=v|X_{0}=u_{0})\) represent the conditional probability of starting from node \(u_{0}\) to reach node \(v\) after \(k\) steps. Following the Bayesian rule, we can get  
\[Pr(X_{k}=v|X_{0}=u_{0})=\sum\limits_{v^{\prime}\in V_{k}}Pr(X_{k-1}=v^{\prime }|X_{0}=u_{0})Pr(X_{k}=v|X_{k-1}=v^{\prime}) \tag{9}\]There are two choices at each node during random walking:  
1. Continue the walking process along a route with the probability \(\alpha\).
2. Skip back to the initial node \(u_{0}\) with probability \(1-\alpha\). In this paper, \(\alpha\) is assigned to 0.85 following the suggestion of [PERSON] et al. [35].  
In detail, if node \(v\) is not node \(u_{0}\) (\(v\
eq u_{0}\), the first case), then we have  
\[\begin{array}{ll}Pr(X_{k}=v|X_{0}=u_{0})&=\sum\limits_{v^{\prime}\
eq V_{v} }Pr(X_{k-1}=v^{\prime}|X_{0}=u_{0})Pr(X_{k}=v|X_{k-1}=v^{\prime})\\ &=a^{k}M^{k-1}P_{0}M_{v}^{T}\end{array} \tag{10}\]  
If node \(v\) is node \(u_{0}\) (\(v=u_{0}\), the second case), then we have  
\[Pr(X_{k}=v|X_{0}=u_{0})=\alpha^{k}M^{k-1}P_{0}M_{v}^{T}+(1-\alpha) \tag{11}\]  
In summary, we have  
\[Pr(X_{k}=v|X_{0}=u_{0})=\left\{\begin{array}{ll}\alpha^{k}M^{k-1}P_{0}M_{v}^ {T},v\
eq u_{0}\\ \alpha^{k}M^{k-1}P_{0}M_{v}^{T}+(1-\alpha),v=u_{0}\end{array}\right. \tag{12}\]  
where \(M_{v}^{T}\) is the \(v\)th column vector of the probability transition matrix \(M\), and each element in \(M_{v}\) represents the transition probability of a certain node moving to node \(v\). \(P_{0}\) is the initial probability distribution vector in random walk. In the beginning of random walk, there is only one node as the start node, that is, the probability starting from the current node is 1, and from other nodes is 0. Take the toy example in Figure 5 to explain. Assume that the target node is node \(u_{1}\), then the initial probability distribution vector is  
\[P_{0}=(1,0,0,0)\]  
In another case, if the target node is node \(u_{2}\), then the initial vector is  
\[P_{0}=(0,1,0,0)\]  
The rest of cases that the target node is some other nodes can be done in the same way.  
Considering that it will lead to high complexity if we use Equation (12) directly, in this paper, we construct a matrix to organize the whole probability distribution. At the beginning of the random walk, only one node is selected to be the start node, then the initial probability distribution matrix is  
\[P_{0}=\left[\begin{array}{ccc}1&\ldots&0\\ \vdots&\ddots&\vdots\\ 0&\cdots&1\end{array}\right]\]  
If the number of users is \(M\), and the initial probability distribution matrix \(P_{0}\) is identity matrix \((P_{0}\in R^{m\times m})\). Based on Equation (12), the probability distribution matrix after random walking with \(k\) steps is  
\[P_{k}=(1-\alpha)P_{0}+\alpha M^{T}P_{k-1} \tag{13}\]  
Along with the step \(k\) being infinite, the probability will converge to be stable, which is decided by the steady state distribution of the Markov chain. Equation (13) can be further transformed into the following Equation (14), and the visiting probability matrix \(P^{*}\).  
\[P^{*}=(1-\alpha)(I-\alpha M^{T})^{-1}P_{0} \tag{14}\]The using probability reflects the improved user similarity. A larger visiting probability means a higher similarity.