1、 本 科 毕 业 论 文 基于 复杂 邻接矩阵 和散列函数 的 图 同构 算法 Graph Matching Algorithm Based on Complicated Adjacency Matrix and Hash Function 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年 月 摘 要 本文首先介绍了图同构问题以及之前的相关研究，指出图同构问题在算法研究领域的地位。图同构问题是目前少数几个既没有被归为 NP 完全问题，也没有被归为 P 问题的 NP 问题，目前还没有多项式复杂度的算法。然后总结了图同构的各种算法，通过比较分析，发现了
2、现有图同构算法所具有的共性，指出了目前的一些算法的优缺点。接着给出了图同构问题的数学定义，结合矩阵的概念给出了图同构更具体的数值计算的表述方式，用更接近图同构问题的数学本质的方法来理解和解决问题。 本文结合传统的图同构算法的结构设计，从数学的角度提取图同构更接近其本质的性质给出具体的计算方法，采用了改进的复杂邻接矩阵作为图的存储结构，实现了用成熟的数学模型来表述图，并且使用散列函数的概念来实 现具体的算法。 本文所实现的 CAMH 算法明显优于传统的图同构算法，在计算方法上也比现有的各种算法更简单，在较好情况下算法复杂度为 O(n2)。但是如果参与比较的图出现自同构现象或者 Hash 冲突情况
3、会大大增加算法运算量，这种情况只有在给出进一步的数学研究成果后才可能解决。在图挖掘中往往不仅要求判断两图是否等价，还要得出两图中节点的对应关系，这无形中也增加了图同构算法的复杂度。 关键词： 图挖掘 ； 复杂邻接矩阵 ； 图同构 Abstract This paper introduces the problem of graph matching and the related researches firstly, and indicates the position of graph matching problem in algorithm research. Graph matchi
4、ng problem is one of a few NP-problems which havent been proved to be NPC-problem or P-problem, and there is no polynomial algorithm. Then it summarizes some recent algorithms of graph matching problem, and discovers that all these algorithms have a comman characteristic. It also gives the mathemati
5、cs concept of graph matching, and a formulation of graph matching using matrix, which are easy to be processed by computer. This paper gives a new graph matching algorithm, CAMH, which conbines the structure of classical graph matching algorithms and new mathematic characteristics, uses a developed
6、mathematic model, improved complex adjacency matrix, to store and describe a graph, and implies a specific algorithm using a hash function. The algorithm in this paper is better than classical graph matching algorithms obviously, and its computing method is easier than recent algorithms. Its average
7、 time complex is O(n2) in good conditions, but the amout of computation will increases heavily when the graph is self-isomorphic or hash conflict occurs. This problem can be solved only when there is new achievement in mathematic. Especially in graph mining， it needs not only to judge whether the tw
8、o graph are equivalence， but also the mapping of the nodes. This also increases the time complexity of graph matching algorithm. Keywords: Graph Mining; Complicated Adjacency Matrix; Graph Matching 目 录 第一章 绪论 . 1 1.1 研究背景及选题意义 . 1 1.2 研究现状及存在问题 . 2 1.3 主要研究内容及特色 . 4 1.4 本文结构安排 . 4 第二章 当前主要的图同构算法 . 5
9、 2.1 图同构问题 . 5 2.2 电路模拟法 . 7 2.3 关联度和出入度序列算法 . 11 2.4 基于邻接矩阵的图同构算法研究 . 18 2.5 特征向量法 . 19 2.6 图同构算法的分析 . 22 2.7 小结 . 23 第三章 CAMH 算法设计与实现 . 24 3.1 复杂邻接矩阵 . 24 3.2 图同构的数学解释 . 26 3.3 CAMH 图同构算法 . 27 3.3.1 CAMH 算法思想 . 27 3.3.2 CAMH 算法设计 . 28 3.4 小结 . 31 第四章 实验与结构分析 . 32 4.1 系统实现 . 32 4.1.1 isomorph 包 . 3
10、3 4.1.2 matrix 包 . 34 4.1.3 classic 包 . 37 4.2 实验结果及分析 . 38 4.3 算法复杂度分析和存在的问题 . 43 4.4 小结 . 44 第五章 总结与展望 . 45 致谢语 . 46 参考文献 . 47 Content Chapter 1 Introduction . 1 1.1 Research Background . 1 1.2 Present Research and Problems. 2 1.3 Main Characteristic . 4 1.4 Contents and Organization . 4 Chapter 2
11、 Related Work . 5 2.1 Graph Matching Problems . 5 2.2 Circit Simulation . 7 2.3 Degree of Association and I/O. 11 2.4 Adjacency Matrix Based Algorithms . 18 2.5 Eigen System . 19 2.6 Graph Matching Algorithms Analysis . 22 2.7 Summary . 23 Charpter 3 CAMH Algorithm Approach . 24 3.1 Complicated Adja
12、cency Matrix . 24 3.2 Math Principle of Graph Matching . 26 3.3 CAMH Graph Matching Algorithm. 27 3.3.1 CAMH Algorithm idea. 27 3.3.2 CAMH Algorithm Design. 28 3.4 Summary . 31 Charpter 4 Experiment and Analysis . 32 4.1 Application . 32 4.1.1 Package isomorph. 33 4.1.2 Package matrix. 34 4.1.3 Pack
13、age classic. 37 4.2 Result and Analysis . 38 4.3 Complexity of the Algorithm . 43 4.4 Summary . 44 Charpter 5 Conclusions and future works . 45 Acknowledgement . 46 References . 47 基于复杂邻接矩阵和散列函数的图同构算法 1 第一章 绪论 1.1 研究背景 及选题意义 与一般意义上的“图像”概念不同，这里的“图”指的是图论意义上的图，它由一些节点以及连接节点的边构成，经常用来表示一些实体和实体间的关系。图挖掘就是对这
14、种关系数据进行挖掘从而得到有价值的信息和模式。而 图挖掘中普遍使用了 图同构 的算法，而且经常要频繁 地 将某一大图中的子图与目标图进行比较。 比如为了判断一个子图是否为频繁，必须统计该子图的重复出现的次数，这时就要 遍历原图中的子图并将该子图与目标图进行比较。不难想象，这种两图间进行比较的次数是原图节点个数的指数级。 这就使得 图同构 算法的运行效率直接影响到图挖掘算法的时空复杂度 ，选用一个好的 图同构 算法能在根本上提高图挖掘算法的效率 。 但是对于图的匹配目前还没有一个多项式级的好算法。 理论上 可以证明 图同构 算法属于 NP 问题，即它的结果的验证时间为多项式级，但是仍然没有对它的
15、求解时间的证明 。 也就是说既不能说它 的复杂度 是多项式级， 也不能说一定不是多项式级 ，因此研究 图同构 的算法是有意义的， 一个 图同构 的快速算法 将直接改进大部分图挖掘算法的运行效率。 在图挖掘中往往不仅要求判断两图是否等价，还要得出两图中节点的对应关系，这无形中也增加了 图同构 算法的复杂度。 因为两图是否等价这个问题的结果只有一个，真或假，而如果两图等价得出的节点的对应关系则可能不止一种 。要处理 n 个节点并且要产生 m（ 0mn!） 个结果， 所用的时间至少为 n m， 这在增加 图同构 算法的复杂度的同时也放宽了限制，只要 能满足 平均时间消耗较低，而且可以通过多次低时间复
16、杂度的计算排除绝大部分错误答案 ，就可以称为 好算法。 图的经典存储结构包含邻接矩阵、邻接表、十字链表等，其中邻接矩阵表示法与其他表示法不同，它不是对图的简单模拟，而是抽象为一种数学概念 矩阵，这有助于从本质上解释图同构的概念，也可以从数学的角度给出更直接更高效的算法。 已经有很多图论或者计算机算法上的，借助矩阵和它的一些特性解决基于复杂邻接矩阵和散列函数的图同构算法 2 图同构 问题的尝试，但是 传统的邻接矩阵表示法仍然不足以表示图挖掘中的复杂图，必须使用复杂化的邻接矩阵。 本文就是总结和 图同构 相关的各方面的研究成果和结论，尝试给出一个好的 图同构 算法，从而有助于解决更多图相关的计算问
17、题。 不仅在图挖掘 领域需要处理图之间的同构关系，由于图同构是非常经典的数学图论问题，因此在很多其他领域 也 都有应用。比如在化学的分子结构研究上，将一个分子看成图之后，就可以将分子和分子间的同构比较看作图和图的同构判定；在社会关系 研究领域，将人与人之间的关系网看作图，就可以将团体间的同构比较看作图和图的同构判定。此外还有很多方面可以利用图的同构算法，因此解决同构算法对各方面的计算都有很大的促进作用。 1.2 研究现状及存在问题 图的同构判定问题是图论学科中的基本问题之一 。 所谓图的同构 ， 就是两个图的结构完全相同 。 有人试图用图的一组不变量来确定图的同构 ， 如回路数、树数、连通片数
18、等 ， 这些尝试都归于失败 1,2。 因为不同构的图也会出现完全相同的不变量 ， 有人 3曾经认为图的邻接矩阵的特征多项式和特征值可能是图的同构判据 ， 结果依然失败了 ， 因为不同构的图也可能有相同的特征多项式和特征值 。多年来 ， 人们一直在寻找一种有效的同构判定方法 ，但是对于图的匹配目前还没有一个多项式级的好算法。 理论上 可以证明图同构算法属于 NP 问题 4-9，即它的结果的验证时间为多项式级，但是仍然没有对它的求解复杂度的证明。也就是说既不能说它的复杂度是多 项式级，也不能说一定不是多项式级。如果使用穷举法计算，则需要依次尝试 n个节点的全排列才能得出所有的结果，时间复杂度大于O
19、（ n!） 。 目前 ， 研究人员在同构判定问题上提出了一些新方法 ， 如将同构问题等效转换的电路模拟法 10,11、 以拓扑图的图论特性为依据的关联度序列法 3和出入度序列法 4、 基于 Hopfield 网络的图同构判定算法 5等 ， 它们在判定的速度与准确性上都取得新的进展 。 但 一些 文献 10,11 12只能处理不含权值的无向图 ； 李锋 等人则针对不含权的有向图 13； 基于 Hopfield 网络的方法可能导致网络运行至不希望的吸引子或吸引环内 ， 而使判定速度变慢 1415。 现有的算法都没有从根本上解决同构的问题，仍然是在进行穷举求解，只不基于复杂邻接矩阵和散列函数的图同构
20、算法 3 过通过各种各样的约束条件进行剪枝，缩小穷举的范围。并且 由于各自的局限性，现有的各种算法都不算一个好的算法，无法解决图挖掘中的图同构问题 。 而且所有的算法都止于得出两图是否同构，对于图中节点的各种对应 关系 都没有进行计算。 除了 Hopfield 网络 算法之外，考虑其他的各种同构算法，如果抛开它们给出的各种解释，只观察它们的计算过程则不难发现，所有的算法都包含三个步骤。 假设两个图的节点数目都是 n，第一步对两个图分别计算 n 个数值序列：在电路模拟法中求出了 n-1个节点的节点电压，加上假设的第一个节点为基准电压，共有 n个数值；在关联度序列和出入度序列算法中，直接用每个节点
21、的拓扑特征信息求出 n 个数值；在特征值系统算法中，由于 n 阶方阵有 n 个特征值和 n 个特征向量，这样就计算出了 n 个数值。在这一步上各种算法都有自己的计算方法和解释，但求得的结果和内涵其实都是一样的。 第二步，将两个图的两组数值序列进行配对，它们的对应关系实际上就代表了节点的对应关系，这样就求出了几种可能的同构变换。第三步必须对这些可能的同构对应关系进行验证，如果验证成功，则两图同构。 因此除非在数学上取得了突破性进展，给出了图同构的更简单有效的充分必要条件，否则同构算法就仍然要使用这三步的计算方法，只不过在第一步求 n个数的数值序列时有可能找到更有效的算法。而有些算法看似复杂而有效，综合使用了其他学科的知识，或者采用了数学中更复杂的概念和计算，但是并没有做出实质上的突破，不能摆脱那三个步骤的 约束 ，甚至在第 一步求解数值序列的时候也没有好的表现。 因此 图同构算法的主要改进方法有三种 ： 1. 寻找一个图同构的容易进行验证的充分条件，这样可以一劳永逸的解决图同构问题，同时这也意味着证明图同构问题是属于 P 问题的；然而这种方式显然更依赖于数学上的进步和图论上新的研究成果，目前仍没有大的进展。 2. 寻求图的等价表示方法，将图进行转化为新的数学模型之后寻找一个解决同构问题的方法。 3. 进一步改进三个步骤中的第一步，使用更严格的必要条件排除非同构的
