## 2 Link-Based Similarity Measures  
In this section, we briefly explain SimRank [11], a well-known link-based similarity measure (in short, similarity measure), and its state-of-the-art variants as JacSim [1], JPRank [17], and SimRank* [9]; their corresponding mathematical formulations are represented in Appendix A.1, in detail.  
**SimRank:** it computes the similarity between two nodes in a graph based on a philosophy that \"two objects are similar if they are related to similar objects\" [11]. For a node-pair \((a,b)\) in a graph, let \(I_{a}\) and \(I_{b}\) be two sets of nodes directly pointing to nodes \(a\) and \(b\), respectively. In SimRank, the similarity score of \((a,b)\) is _iteratively_ computed as the _average_ of similarity scores of _all possible node-pairs_\((i,j)\) where node \(i\) belongs to \(I_{a}\) and node \(j\) belongs to \(I_{b}\); this computation manner is called a _pairwise normalization paradigm_[1]. Consider a sample graph in Figure 1; SimRank considers nodes \(e\) and \(f\) similar since they are directly pointed to by common node \(b\) (each node is highly similar to itself) and nodes \(i\) and \(j\) are regarded as similar since they are indirectly pointed to by common nodes \(c\) and \(d\).  
**JacSim:** it tries to solve the _pairwise normalization problem_, by employing both Jaccard and pairwise normalization paradigm in similarity computation. This problem is a counter-intuitive property of SimRank where the SimRank score of a pair of nodes commonly pointed to by a _large_ number of nodes tends to be _lower_ than that of another pair of nodes commonly pointed to by a _small_ number of nodes [1; 16; 20]. As an example, consider node-pairs \((i,h)\) and \((i,j)\) in the graph of Figure 1 where the similarity scores of some node-pairs are shown as well (We note that all the scores are computed by employing the matrix form of SimRank, JacSim, and JPRank); nodes \(i\) and \(h\) are pointed to by a single common node \(b\), while nodes \(i\) and \(j\) are pointed to by two common nodes \(c\) and \(d\). However, the SimRank score of \((i,h)\) (i.e., 0.0106) is bigger than that of \((i,j)\) (i.e., 0.0071) due to the pairwise normalization problem, while, as shown in the figure, the JacSim score of \((i,h)\) (i.e., 0.0048) is smaller than that of \((i,j)\) (i.e., 0.0076).  
**SimRank***:** it is a variant of SimRank trying to remedy the _level-wise computation_ problem in SimRank; this problem happens since SimRank regards two nodes similar if some paths _only_ with _equal length_ exist from a common node to both of them. As an example, consider the node-pair \((e,i)\) in Figure 1; there are no paths with the equal length from any common nodes such \(b\) to them. There is a path with length two from \(b\) to \(i\), while there is a path with length one from \(b\) to \(e\). Therefore, the SimRank score of \((e,i)\) becomes zero as shown in the figure due to the level-wise computation problem; however, their SimRank* score is not zero (i.e., 0.0206).  
**JPRank:** it is another variant of SimRank that solves both the pairwise normalization and _in-links consideration_ problems. The latter problem arises since SimRank considers only in-links to compute the similarity score. As an example, in Figure 1, the SimRank score of node-pair \((b,c)\) is zero since \(l_{b}=l_{c}=\emptyset\). However, both \(b\) and \(c\) are pointing to a common node \(f\), which means \(b\) and \(c\) are somehow similar; as shown in the figure, the JPRank score of \((b,c)\) is not zero (i.e., 0.0028).  
It is worth noting that, although our sample graph in Figure 1 is directed, all the above similarity measures can be applied to undirected graphs as well. However, the in-links consideration problem is _not_ applicable to an undirected graph and JPRank behaves exactly the _same_ as JacSim in similarity computation [17].