基于代价矩阵的近似图匹配算法研究

发布时间：2021-04-28 09:01

　　图匹配是衡量两个图之间相似性的过程,在模式识别,社交网络,医药学等多个领域早已广泛应用。近几十年来,研究者们提出了大量解决图匹配问题的算法。其中,图编辑距离作为解决图匹配问题最常用的方法已受到越来越多的关注。目前,对图编辑距离问题的研究主要分为近似图编辑距离和精确图编辑距离,本文针对基于近似图编辑距离的匹配算法进行研究。首先,介绍了与图相关的基本知识,以及图编辑距离的相关概念,并对相关算法及实现过程进行了简要介绍。其次,分析SFBP（Square Fast Bipartite）代价矩阵在构建过程中存在精确度缺失的问题,提出一种新的代价矩阵。通过计算目标图和源图中任意两个节点的添加、删除之和,将其与SFBP代价矩阵中的相应节点进行替换,得到新的代价矩阵。再次,对基于新的代价矩阵进行求解的图匹配算法进行改进并提出RC-Greedy算法。已有算法在使用贪婪策略选取分配节点的过程中,优先从代价矩阵的行的角度去考虑节点的大小,没有考虑节点在其所在列中的大小,存在精确度缺失问题。通过从列的角度获取次优分配节点,增加对比节点的数量,更加全面的考虑分配情况,从而得到更优的分配结果。最后,基于GREYC... 

【文章来源】：燕山大学河北省

【文章页数】：55 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 研究背景和意义
    1.2 国内外研究现状
        1.2.1 图匹配
        1.2.2 图编辑距离
    1.3 本文研究内容
    1.4 论文结构
第2章 基础知识概述
    2.1 图的基本知识
    2.2 图编辑距离的相关知识
        2.2.1 图编辑操作
        2.2.2 图编辑距离的定义
        2.2.3 图编辑距离的代价函数
    2.3 基本算法
        2.3.1 子图同构算法
        2.3.2 图编辑距离算法
    2.4 本章小结
第3章 代价矩阵的改进
    3.1 引言
    3.2 SFBP代价矩阵分析
        3.2.1 基本代价矩阵
        3.2.2 SFBP代价矩阵的构建
        3.2.3 SFBP代价矩阵存在的问题
    3.3 N_SFBP代价矩阵
        3.3.1 针对SFBP代价矩阵的改进策略
        3.3.2 N_SFBP代价矩阵的构建算法
    3.4 本章小结
第4章 基于N_SFBP代价矩阵的近似图匹配算法
    4.1 引言
    4.2 GLA算法分析
        4.2.1 GLA算法的求解过程
        4.2.2 GLA算法存在的问题
    4.3 RC-GREEDY算法
        4.3.1 定义RC-Greedy算法的代价函数
        4.3.2 针对GLA算法的改进策略
        4.3.3 对N_SFBP代价矩阵进行预处理
        4.3.4 RC-Greedy算法设计
    4.4 本章小结
第5章 实验与结果分析
    5.1 引言
    5.2 实验环境和数据集
    5.3 实验评价指标
    5.4 实验结果及分析
        5.4.1 SFBP和 N_SFBP代价矩阵性能比较
        5.4.2 GLA和 RC-Greedy算法性能比较
    5.5 本章小结
结论
参考文献
攻读硕士学位期间承担的科研任务与主要成果
致谢


【参考文献】：
期刊论文
[1]图匹配技术研究[J]. 项英倬,谭菊仙,韩杰思,石浩.  计算机科学. 2018(06)
[2]图编辑距离概述[J]. 徐周波,张鵾,宁黎华,古天龙.  计算机科学. 2018(04)
[3]大规模图数据匹配技术综述[J]. 于静,刘燕兵,张宇,刘梦雅,谭建龙,郭莉.  计算机研究与发展. 2015(02)



本文编号：3165201