# StructSim: Meta-Structure-Based Similarity Measure in Heterogeneous Information Networks
## 3 The Proposed Method
### The Implementation of StructSim
#### 3.4.2 Expansion Probability Matrix with Bias  
Based on the Node-Composition Operator, we can easily define the expansion probability matrix with bias as follows.  
Figure 3: A toy example of the Node-Composition operator.  
**Definition 2**.: _Expansion probability matrix with bias. \(W_{ij}\) is an adjacent matrix between \(S[i]\) and \(S[j]\). The normalized matrix of \(W_{ij}\) along the row vector is denoted as \(U_{ij}\), which is the expansion probability matrix of layer relation \(S[i]\ \overset{R}{\rightarrow}S[j]\). Suppose there exists bias \(\delta\) for \(S[i]\) expanding to different objects in \(S[j]\) of the same layer \(j\). The expansion probability matrix with bias \(U_{ij}(\delta)\) of layer relation \(S[i]\ \overset{R}{\rightarrow}S[j]\) is \(U_{ij}(\delta)=f\big{(}U_{ij},M(\delta)_{i}\big{)}\). \(f\big{(}U_{ij},M(\delta)_{i}\big{)}\) is the function of matrices \(U_{ij}\) and \(M(\delta)_{i}\) and \(M(\delta)_{i}\) is the bias matrix of object type in the \(i\)th layer based on layer relation \(S[i]\ \overset{R}{\rightarrow}S[j]\)._  
\(M(\delta)_{i}\) denotes that the object in the \(i\)th layer of the meta structure \(S\) has a different bias for various objects in the (\(i\)+1)th layer. The probability is the same in each row of the expansion probability matrix \(U_{ij}\), while the probability may be different in each row of the expansion probability matrix with bias \(U_{ij}(\delta)\). \(S[i]\) denotes the node sets in the \(i\)th layer of the meta structure \(S\). It is obvious that \(S[i]\) has two different situations. One is that \(S[i]\) only contains a node. The other is that \(S[i]\) contains more than one node. In the first situation, it is easy to compute the expansion probability matrix with bias by adopting the existing transition probability matrix. However, it is very difficult to calculate the expansion probability matrix with bias in the second situation. As illustrated in the Node-Composition Operator, \(S[i]\) is regarded as a whole when making subgraph expansion based on a meta structure. Therefore, we first use the Node-Composition Operator for \(S[i]\). Then, we adopt a strategy similar to the first situation to calculate the probability matrix.  
In this paper, we present the weighted combination operation to determine the function \(f\). That is, \(U_{ij}(\delta)=f\big{(}U_{ij},M(\delta)_{i}\big{)}=\omega U_{ij}+(1-\omega)M( \delta)_{i}\). Based on the expansion probability matrix with bias \(U_{ij}(\delta)\), we have the following relevance matrix \(SM_{structsim}(S)\) between the type of source node \(o_{s}\) and the type of target node \(o_{t}\) based on the meta structure \(S\) for StructSim.  
\[SM_{structsim}(S)=U_{12}(\delta)U_{23}(\delta)\cdots U_{(d_{s}-1)d_{s}}(\delta) \tag{4}\]  
where \(d_{S}\) denotes the total number of layers in the meta structure \(S\). We can obtain the final similarity score \(SM_{structsim}(S)\) based on the meta structure by way of matrix multiplication, which refers to the \(StructSim(x,y|S)\) in Equation (1).