Assessing single-pair similarity over graphs by aggregating first-meeting probabilities

作者：

Highlights：

• We propose an approach to compute similarity of a single node pair, avoiding computation of similarities of other node pairs.

• We prove that the method computes similarity without accuracy loss and its time cost is less than all-pair SimRank.

• We propose position probability and position matrix to facilitate the implementation of the proposed approach.

• Comprehensive experiments are conducted on both synthetic datasets and real datasets to demonstrate its accuracy and efficiency.

摘要

Highlights•We propose an approach to compute similarity of a single node pair, avoiding computation of similarities of other node pairs.•We prove that the method computes similarity without accuracy loss and its time cost is less than all-pair SimRank.•We propose position probability and position matrix to facilitate the implementation of the proposed approach.•Comprehensive experiments are conducted on both synthetic datasets and real datasets to demonstrate its accuracy and efficiency.

论文关键词：Graph mining,Similarity measure,Algorithm,Link graph,SimRank,First-meeting probabilities

论文评审过程：Received 30 July 2012, Revised 29 July 2013, Accepted 24 December 2013, Available online 7 January 2014.

论文官网地址：https://doi.org/10.1016/j.is.2013.12.008