图的相似性描述与匹配方法的研究及其应用

论文摘要

图的相似性和匹配是一个重要的研究领域，在数学问题，生物和化学领域，数据挖掘，网络应用等许多方面都有着广泛的应用。万维网的出现在许多领域催生了大规模的海量统计数据，节点关系图是呈现关系数据结构最直观的方式，在各种研究和应用领域中广泛的采用，因此大规模图作为数据的表现方式，具有十分重要的研究意义。图的搜索匹配算法属于图同构判定的问题，一般情况下无法在多项式时间之内求解，是一个NP完全问题，传统方法的高开销无法适应许多大数据量应用的需要。而优化算法的特殊性也无法应用在一般的情况。为了提高图的搜索和匹配效率，将提出一种建立在一个迭代计算图相似性理论的基础之上的算法。算法的核心思想是利用相关点和边之间的相似度进行迭代计算，然后证明了迭代收敛的规则并给出了算法的下界，将迭代公式用矩阵形式表示，并且利用矩阵性质进行简化。计算出图之间的任意点和边相似性的完整描述，通过一些简化方法提高求解效率，计算图之间匹配的相似度。最后将给出一个计算机软件相似性研究的应用实例，利用类图匹配结果来得到软件之间的相似度，通过两组实验的横向和纵向对比，实验结果证明了提出算法的有效性和可行性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究的背景
• 1.2 国内外研究现状
• 1.3 主要研究工作
• 2 图相似性算法研究基础
• 2.1 图算法的理论基础
• 2.2 图相似性和匹配问题的描述
• 2.3 本章小结
• 3 图相似性描述
• 3.1 概述
• 3.2 图的表示方法
• 3.3 图节点与边的相似度计算
• 3.4 相似性收敛定理及证明
• 3.5 迭代公式简化
• 3.6 图的匹配及相似值
• 3.7 本章小结
• 4 图匹配算法的设计与应用
• 4.1 在软件相似性问题中的应用
• 4.2 类图数据的获取和抽象
• 4.3 算法实验
• 4.4 本章小结
• 5 总结与展望
• 5.1 全文总结
• 5.2 展望
• 致谢
• 参考文献