ASCOS++: An Asymmetric Similarity Measure for Weighted Networks to Address the Problem of SimRank

摘要

In this article, we explore the relationships among digital objects in terms of their similarity based on vertex similarity measures. We argue that SimRank-a famous similarity measure-and its families, such as P-Rank and SimRank++, fail to capture similar node pairs in certain conditions, especially when two nodes can only reach each other through paths of odd lengths. We present new similarity measures ASCOS and ASCOS++ to address the problem. ASCOS outputs a more complete similarity score than SimRank and SimRank's families. ASCOS++ enriches ASCOS to include edge weight into the measure, giving all edges and network weights an opportunity to make their contribution. We show that both ASCOS++ and ASCOS can be reformulated and applied on a distributed environment for parallel contribution. Experimental results show that ASCOS++ reports a better score than SimRank and several famous similarity measures. Finally, we re-examine previous use cases of SimRank, and explain appropriate and inappropriate use cases. We suggest future SimRank users following the rules proposed here before naievely applying it. We also discuss the relationship between ASCOS++ and PageRank.