大规模图上的SimRank计算研究综述

SimRank是一种衡量有向图中任意两节点间结构相似度的模型,其主要思想为,若图中两个节点被相似节点引用,则这两个节点相似.SimRank计算的相似度被广泛应用到网络图聚类、近似查询和协同过滤等领域.SimRank计算模型是一个递归模型,其计算时间、空间复杂度非常高,很难应用于大规模图计算.过去十几年,研究者们针对大规模图提出了许多高效或近似计算的SimRank计算算法.本文首先介绍SimRank模型的描述,以及常见的SimRank计算问题定义,然后按照计算方式将这些算法分为迭代法、非迭代法与随机游走法三类;将非迭代法分为基于矩阵运算求解、基于节点对图求解以及基于线性表示求解,将随机游走法分为基于不同索引结构求解、基于不同抽样方式求解以及其他随机游走算法;介绍了这些算法的基本概念、计算原理以及算法特点;分析了随机游走法与迭代法、非迭代法之间的关系;对各种算法的时间复杂度、空间复杂度、计算精确度以及可扩展性进行了论述;在此基础总结了这些SimRank算法所对应的计算场景,主要包括单点对/单源(Single Pair/Single Source)查询问题、全体/部分节点对(All Pair/Partial Pair)计算问题以及查询问题.最后对不同算法实验中图的规模进行了总结,并对大规模图上的SimRank计算方法进行了总结和展望.