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

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 <italic>pairwise normalization problem</italic>; 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 <italic>JacSim&#x002A;</italic> to effectively <italic>solve</italic> them; JacSim&#x002A; <italic>exploits</italic> those paths neglected by JacSim in similarity computation, its matrix form provides the <italic>exact</italic> similarity scores while <italic>not</italic> being sensitive to the number of node-pairs with common neighbors, and it has simpler, easier to understand, and easier to implement formulas in <italic>both</italic> iterative and matrix forms than those of JacSim. We conduct extensive experiments with <italic>eight</italic> real-world datasets to evaluate <italic>both</italic> the accuracy and performance of JacSim&#x002A; in comparison with those of JacSim. Our experimental results demonstrate that JacSim&#x002A; shows <italic>better</italic> accuracy than JacSim and the JacSim&#x002A; matrix form is <italic>dramatically</italic> faster than its own iterative form and also than the two forms of JacSim with <italic>all</italic> datasets.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.