文献详情
大规模图上的SimRank计算研究综述
外文标题：Research Progress of SimRank Computation on Big Graph: A Survey
文献类型：期刊
期刊名称：计算机学报
年：2019
卷：42
期：12
页码：2665-2682
ISSN：0254-4164
关键词：结构相似度;SimRank计算;随机游走;算法分析;复杂度分析
所属部门：信息学院；数据工程与知识工程教育部重点实验室
链接地址：http://d.oldg.wanfangdata.com.cn/Periodical_jsjxb201912005.aspx
摘要：SimRank是一种衡量有向图中任意两节点间结构相似度的模型,其主要思想为,若图中两个节点被相似节点引用,则这两个节点相似.SimRank计算的相似度被广泛应用到网络图聚类、近似查询和协同过滤等领域.SimRank计算模型是一个递归模型,其计算时间、空间复杂度非常高,很难应用于大规模图计算.过去十几年,研究者们针对大规模图提出了许多高效或近似计算的SimRank计算算法.本文首先介绍SimRank模型的描述,以及常见的SimRank计算问题定义,然后按照计算方式将这些算法分为迭代法、非迭代法与随机游走法三类;将非迭代法分为基于矩阵运算求解、基于节点对图求解以及基于线性表示求解,将随机游走法分为基于不同索引结构求解、基于不同抽样方式求解以及其他随机游走算法;介绍了这些算法的基本概念、计算原理以及算法特点;分析了随机游走法与迭代法、非迭代法之间的关系;对各种算法的时间复杂度、空间复杂度、计算精确度以及可扩展性进行了论述;在此基础总结了这些SimRank算法所对应的计算场景,主要包括单点对/单源(Single Pair/Single Source)查询问题、全体/部分节点对(All Pair ...More
SimRank是一种衡量有向图中任意两节点间结构相似度的模型,其主要思想为,若图中两个节点被相似节点引用,则这两个节点相似.SimRank计算的相似度被广泛应用到网络图聚类、近似查询和协同过滤等领域.SimRank计算模型是一个递归模型,其计算时间、空间复杂度非常高,很难应用于大规模图计算.过去十几年,研究者们针对大规模图提出了许多高效或近似计算的SimRank计算算法.本文首先介绍SimRank模型的描述,以及常见的SimRank计算问题定义,然后按照计算方式将这些算法分为迭代法、非迭代法与随机游走法三类;将非迭代法分为基于矩阵运算求解、基于节点对图求解以及基于线性表示求解,将随机游走法分为基于不同索引结构求解、基于不同抽样方式求解以及其他随机游走算法;介绍了这些算法的基本概念、计算原理以及算法特点;分析了随机游走法与迭代法、非迭代法之间的关系;对各种算法的时间复杂度、空间复杂度、计算精确度以及可扩展性进行了论述;在此基础总结了这些SimRank算法所对应的计算场景,主要包括单点对/单源(Single Pair/Single Source)查询问题、全体/部分节点对(All Pair/Partial Pair)计算问题以及查询问题.最后对不同算法实验中图的规模进行了总结,并对大规模图上的SimRank计算方法进行了总结和展望. ...Hide

DOI：10.11897/SP.J.1016.2019.02665
百度学术：大规模图上的SimRank计算研究综述
语言：中文
基金：国家重点研发计划; 国家自然科学基金
作者其他论文



联合建模异构社交和内容信息的活动推荐模型.王绍卿, 王征, 李翠平, et al. .软件学报. 2018, 29(10), 3134-3149.
联合建模异构社交和内容信息的活动推荐模型.王绍卿, 王征, 李翠平, et al. .软件学报. 2018, 3134-3149.
无线传感器网络隐私保护数据聚集技术.张晓莹, 彭辉, 陈红,.通信学报. 2018, 130-142.
无线传感器网络隐私保护数据聚集技术.张晓莹, 彭辉, 陈红,.通信学报. 2018, 39(10), 130-142.
一种机器学习中的数据隐私保护方法和系统.秦波, 唐文易, 赵素云, et al. .2018.