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

• 作者: 张良富 李翠平 陈红
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 结构相似度 SimRank计算 随机游走 算法分析 复杂度分析
• 年，卷（期）: 2019,（12）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 2665-2682
• 页数: 18页
• 分类号: TP391
• 字数: 19178字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2019.02665

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈红	中国人民大学信息学院	86	978	16.0	29.0
2	张良富	中国人民大学信息学院	1	1	1.0	1.0