  As a fundamental issue in network analysis, structural node similarity has
received much attention in academia and is adopted in a wide range of
applications. Among these proposed structural node similarity measures, role
similarity stands out because of satisfying several axiomatic properties
including automorphism conformation. Existing role similarity metrics cannot
handle top-k queries on large real-world networks due to the high time and
space cost. In this paper, we propose a new role similarity metric, namely
\textsf{ForestSim}. We prove that \textsf{ForestSim} is an admissible role
similarity metric and devise the corresponding top-k similarity search
algorithm, namely \textsf{ForestSimSearch}, which is able to process a top-k
query in $O(k)$ time once the precomputation is finished. Moreover, we speed up
the precomputation by using a fast approximate algorithm to compute the
diagonal entries of the forest matrix, which reduces the time and space
complexity of the precomputation to
$O(\epsilon^{-2}m\log^5{n}\log{\frac{1}{\epsilon}})$ and $O(m\log^3{n})$,
respectively. Finally, we conduct extensive experiments on 26 real-world
networks. The results show that \textsf{ForestSim} works efficiently on
million-scale networks and achieves comparable performance to the state-of-art
methods.
