JacSim*: An Effective and Efficient Solution to the Pairwise Normalization Problem in SimRank

Abstract

Despite the fact that SimRank has been successfully applied to various applications as a link-based similarity measure, it suffers from a counter-intuitive property called a pairwise normalization problem; JacSim is a powerful variant of SimRank that alleviates this problem. In this paper, we first point out three existing drawbacks of JacSim and then propose JacSim* to effectively solve them; JacSim* exploits those paths neglected by JacSim in similarity computation, its matrix form provides the exact similarity scores while not being sensitive to the number of node-pairs with common neighbors, and it has simpler, easier to understand, and easier to implement formulas in both iterative and matrix forms than those of JacSim. We conduct extensive experiments with eight real-world datasets to evaluate both the accuracy and performance of JacSim* in comparison with those of JacSim. Our experimental results demonstrate that JacSim* shows better accuracy than JacSim and the JacSim* matrix form is dramatically faster than its own iterative form and also than the two forms of JacSim with all datasets.

Keywords

• Link-based similarity
• pairwise normalization problem
• similarity computation
• SimRank