Authors: Yue Wang, Zonghao Feng, Lei Chen, Zijian Li, Xun Jian, Qiong Luo
Published in: IEEE Transactions on Knowledge and Data Engineering（TKDE 2019）
Date of Publication: July 30, 2019
Measuring similarities among different nodes is important in graph analysis tasks, such as link prediction, and recommendation. Among different similarity measurements, SimRank is one of the most popular and promising ones, and has received a lot of research attention. While most current studies focus on single-pair, single-source/top-k and all-pairs SimRank computation, few of them have studied finding similar pairs given a set of node pairs, which has attractive applications in personalized search and recommendation tasks. In this paper, we present Carmo, an efficient algorithm for retrieving the top-k similarities from an arbitrary set of pairs. In addition, we introduce two types of indexes to boost the efficiency of Carmo: one is hub-based, the other is tree-based. We shows the effectiveness and efficiency of our proposed methods by extensive experiments.