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

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

论文摘要

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

论文目录

  • 1 引言
  • 2 模型描述与问题定义
  •   2.1 SimRank模型定义
  •   2.2 SimRank计算问题定义
  • 3 SimRank计算方法
  •   3.1 迭代法
  •     3.1.1 基于原图G求解与优化
  •     3.1.2 迭代算法总结
  •   3.2 非迭代法
  •     3.2.1 矩阵运算直接求解
  •     3.2.2 基于节点对图G2精确求解
  •     3.2.3 线性表示求解
  •     3.2.4 非迭代法总结
  •   3.3 随机游走法
  •     3.3.1 基于不同索引结构的SimRank计算
  •     3.3.2 基于不同抽样方式的SimRank计算
  •     3.3.3 基于不同查询方式的SimRank计算
  •     3.3.4 其他随机游走SimRank算法
  •     3.3.5 随机游走算法总结
  • 4 SimRank不同计算方法关系分析
  •   4.1 迭代法与随机游走法之间关系
  •   4.2 迭代法与非迭代法之间关系
  •   4.3 通过G2图计算与通过原图计算关系
  •   4.4 不同算法之间特点
  • 5 SimRank算法复杂度与可扩展性分析
  •   5.1 迭代算法
  •   5.2 非迭代算法
  •   5.3 随机游走算法
  • 6 SimRank计算总结与展望
  •   6.1 SimRank计算总结
  •   6.2 SimRank计算主要挑战与展望
  • Background
  • 文章来源

    类型: 期刊论文

    作者: 张良富,李翠平,陈红

    关键词: 结构相似度,计算,随机游走,算法分析,复杂度分析

    来源: 计算机学报 2019年12期

    年度: 2019

    分类: 信息科技,基础科学

    专业: 数学

    单位: 中国人民大学信息学院,数据工程与知识工程教育部重点实验室(中国人民大学)

    基金: 国家重点研发计划(2018YFB1004401),国家自然科学基金(61772537,61772536,61702522,61532021)资助~~

    分类号: O157.5

    页码: 2665-2682

    总页数: 18

    文件大小: 1107K

    下载量: 293

    相关论文文献

    标签:;  ;  ;  ;  ;  

    大规模图上的SimRank计算研究综述
    下载Doc文档

    猜你喜欢