## 4 Experimental Evaluation
### Wikipedia Dataset
#### Link-Based Similarity Measures  
In order to conduct a fair comparison, we implemented the matrix form of JacSim, JPRank, SimRank*, and SimRank _without_ applying any acceleration techniques such as multi-processing (as the simplest technique), fine-grained memorization [9], partial sums memoization [49], and backward local push and Monte Carlo sampling [50]. Since the execution time could slightly change depending on the system resources such as CPU overload, to obtain an accurate execution time, we run each similarity measure on eight iterations for five times with a dataset and the average run time over the five executions is regarded as the _final_ execution time of the similarity measure. Note that we consider _only_ the elapsed time to compute the similarity scores as the execution time; the required time to store the results of similarity computation in a file or a database is _not_ considered.  
Table 15 shows the execution time (minutes) of similarity measures with our five datasets (As already explained in Section 4.2.1, we do not apply JPRank to undirected graphs BlogCatalog and Wikipedia). With all datasets, SimRank* shows the best efficiency since it requires only _one_ matrix multiplication in Equation (A8). With undirected datasets (i.e., BlogCatalog and Wikipedia), JacSim shows the worst efficiency since it requires two matrix multiplications and a pairwise normalization paradigm to compute matrix \(E\) in Equation (A6). With directed datasets (i.e., Cora, DBLP, and TREC), JPRank shows the worst efficiency since it requires four matrix multiplications and two pairwise normalization  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & & **MAP** & **Precision** & **Recall** & **PRES** & **F-Score** \\ \hline \multirow{2}{*}{DeepWalk with Cora dataset} & \(d=512\) & 0.023 & 0.398 & 0.031 & 0.026 & 0.053 \\  & \(d=1024\) & **0.023** & **0.398** & **0.031** & **0.026** & **0.053** \\ \hline \multirow{2}{*}{Line with Cora dataset} & \(d=512\) & 0.023 & 0.391 & 0.032 & 0.026 & 0.053 \\  & \(d=1024\) & **0.023** & **0.391** & **0.031** & **0.026** & **0.053** \\ \hline \multirow{2}{*}{DeepWalk with TREC dataset} & \(d=32\) & **0.022** & **0.025** & **0.039** & **0.027** & **0.028** \\  & \(d=64\) & 0.026 & 0.033 & 0.054 & 0.035 & 0.038 \\ \hline \multirow{2}{*}{NetMF with TREC dataset} & \(d=512\) & 0.025 & 0.034 & 0.054 & 0.036 & 0.038 \\  & \(d=1024\) & **0.025** & **0.033** & **0.053** & **0.035** & **0.038** \\ \hline \hline \end{tabular}
\end{table}
Table 14: Results of four extra experiments for suspicious cases.  
paradigms to compute matrices \(E\) and \(E^{I}\) in Equation (A10). However, among _all_ the available cases in Table 15, JacSim with the BlogCatalog dataset shows the worst efficiency, although BlogCatalog has less nodes than Cora, DBLP, and TREC datasets. The reason is that there are \"32,787,165\" node-pairs with non-empty common in-link sets in this dataset, which makes the calculation of matrix \(E\) expensive; the number of these node-pairs in Cora, DBLP, TREC, and Wikipedia datasets are \"229,306\", \"466,990\", \"1,391,293\", and \"11,015,803\", respectively.