论文部分内容阅读
随着互联网+在各应用领域的迅猛发展,图结构数据呈指数级的趋势增长。图匹配作为图结构数据的基础算法,在数据挖掘、识别和检索等方面均发挥着关键作用。因此,构建复杂度较低且准确率较高的图匹配算法便显得尤为必要。图谱作为图的一种重要的特征表现形式,近年来在图匹配算法研究领域愈发受到重视。图谱类图匹配方法的核心思想在于通过分析特征矩阵的谱特性,将图的匹配问题转化为各个节点之间的最优匹配问题,从而达到图匹配的目的。此外,图谱对预处理过程中的数据降维、简化计算等均能表现出较好的效果,且能提高大规模图数据的匹配效率。论文以图谱理论为基础,通过分析谱特征的提取方法和构造相应的改进策略,对图谱类图匹配算法进行了研究与探索,主要研究内容总结如下:1.构建了基于关联度矩阵的Laplace谱特征匹配算法。对谱特征的提取方法进行了优化,并引入了关联度矩阵的概念,不仅能够描述节点间的直接相邻关系,也融合了节点间的间接连接信息,较全面的描述了每个节点在整个图结构中的作用与连接位置信息,因此能够对图中的节点进行更明确的层次化区分。进而结合归一化的Laplace矩阵以及其特征向量构造特征矩阵,使用奇异值分解算法对图数据进行特征匹配。实验结果表明该方法能够有效的提高图匹配效率。2.构建了基于相似度矩阵的Kuhn-Munkres算法。充分考虑了图的整体结构特征与内部节点间的相对位置关系,利用节点位置相似度来弥补全局结构矩阵无法描述节点间的相对位置的缺陷。在此基础上利用Kuhn-Munkres算法计算图之间的最大权二分匹配,有效的解决了二分图匹配过程中可能产生局部最优匹配而不能完全考虑全局匹配的缺点。实验结果表明,算法能够达到较好的匹配效果,明显提高了匹配效率。3.构建了位置谱特征下的概率松弛匹配算法。在Laplace谱特征的基础上加入了节点空间位置属性,有效的将具有相似连接关系的节点通过位置信息区分开来。在概率松弛匹配算法中,使用多次迭代的方式对已有的匹配关系进行支持度扩展,在节点的相互匹配中引入条件概率。实验结果表明,通过多次迭代产生的匹配概率矩阵能够得到较好的匹配关系。