一种改进的极大完全子图挖掘算法

摘要：在计算机领域中，图是最复杂的数据结构之一。该文研究了图的挖掘理论及算法。特别针对参考文献[1]中图的极大完全子图算法 “MaxcodeFMCG”（Finding Maximal Complete Subgraph by Maxcode）进行了改进，使算法效率得到提高；并设计了相关数据结构，在Microsoft Visual Studio 2008开发软件平台上，进行仿真实验，寻找出了无向图所对应的所有极大完全子图，实验结果正确。

关键词： 数据挖掘；频繁模式；极大完全子图

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）07-0174-04

1 概述

近年来，数据挖掘引起信息产业界的极大关注，频繁模式挖掘问题的研究也已经成为数据挖掘领域研究的热点之一。寻找频繁模式的两大经典算法是Apriori算法以及FP增长算法，前者采用宽度优先的方法遍历数据，后者则采用深度优先的方法遍历数据，两者都能实现频繁模式的挖掘，但是当数据量很大时，两类算法在执行时都需要占用大量的内存，从而降低了挖掘效率。研究发现：大部分现实中的事务数据都可以转化为一定的图结构，结合图的一些性质，通过寻找图的极大完全子图，实现图划分操作，从而间接地把事务数据划分为若干子事务。通过这种划分方法解决了数据量巨大会导致两个经典算法的执行时内存不足、效率降低等问题，之后只需要任选经典算法中的一个，对划分之后的每个子集进行处理就可事半功倍的得到频繁模式。

2 基本定义和定理

2.1图

论文关注的是无向连通图，并使用图的邻接矩阵表示图的存储结构。

定义1 （邻接矩阵G的code码）设有n个顶点的图G的邻接矩阵A为：

算法思想分析：

基于性质2的讨论，我们可以简化4）和5），因为每次两个K阶矩阵连接之前如果他们对应的code码不全为1，那么连接后生成的K+1阶矩阵对应的code码也一定不全为1，那么之后对K+1阶矩阵生成code码并判断是否全为1的过程也显得徒劳。反之，只有两个K阶矩阵对应的code码全为1，那么之后对两个矩阵连接生成的K+1阶矩阵对应的code码进行判断分析才会有必要。但是如果两个K阶矩阵对应的code码全为1，即连接后生成K+1阶矩阵所对应的code码的前K位一定全为1，那也就是说，若要判断两个矩阵连接生成的K+1阶矩阵对应code码全为1，就只需要判断两个K阶矩阵中不相同的两个顶点之间在当前对应的逆导出子图G’中是否有边相连，若有边相连则K+1阶矩阵对应code码全为1，若无边相连，则K+1阶矩阵对应code码不全为1，其对应的顶点集不属于极大完全子图。

3.2.2改进后的算法思想

算法1：

根据以上分析可知，生成极大完全子图顶点的算法过程的4）、5）、6）部分可以做些改进，如下：

4） 将G’中度最大的顶点V1与G’中其余顶点组合成长度为2的顶点集，并将它们放入Rset中；

5） for（K=2；K

分别将Rset中两个长度为K的顶点序列集进行比较：

如果有它们K-1个顶点相同且存在一个顶点不同，那么继续判断两个不同的顶点在图G’中是否有边相连，如果有边相连则将当前两个顶点集合并后生成的新的长度K+1的顶点集存入Rset中；

否则两个长度为K的顶点进行比较，直到将所有长度为K的顶点集都两两比较完。

6）删除φ（v1）中重复的顶点集，如果φ（v1）中某一顶点序列中某一顶点序列中的所有顶点均出现在另一个顶点序列中，则删除该顶点序列，直到φ（v1）中不存在这样的顶点序列为止。

3.2.3求图的逆导出子图算法设计

算法2：求图的逆导出子图

输入数据：图G

输出图G的逆导出子图

1） 求当前图G中度最大的顶点在顶点表中的下标。

2） G1G，将图G的信息复制给G1。

3）遍历图G1并把图G1中与度最大的顶点有边相连的顶点在图G中对应存储的信息依次全部删除。

4）最后剩余的图信息即为图G的逆导出子图。

3.3.4求图的逆导出补图算法设计

算法3

输入数据：图G，存储逆导出补图Gc的地址，当前图G中度最大的顶点在顶点表中的下标。

输出：图的逆导出补图。

1） 求当前图G中度最大的顶点在顶点表中的下标。

2） GcG。

3）遍历图G1并把图Gc中与度最大的顶点没有边相连的顶点在图G中对应存储的信息依次全部删除。

4）最后剩余的图信息即为图G的逆导出子图。

3.3.5算法具体实现

上述算法在实现过程中用到的数据结构设计如下

1）每个逆导出子图所对应的极大完全子图顶点集数据存储结构

以图G的逆导出子图G1为例，G1所对应的顶点集存储结构示例图如下：

图9 图G1的极大完全子图顶点集存储结构示例

为了简化对堆串中数据的增删改的操作，对堆串的结构进行了适当的改进，同一个Type所对应的顶点序列集存储在同一个连续的存储单元中，反之不同Type的顶点序列集存储在不同的数组中，这样可以减少对顶点序列集操作时的工作量，另外为了在通过K个顶点生成K+1个顶点的过程中方便判断某两个顶点之间是否在当前图逆导出子图中有边相连，为了方便读者理解，本文所有对极大完全子图顶点集的存储结构图示中，标出的是顶点的名称而不是下标。

2）图G的每个逆导出子图所对应的极大完全子图图集的数据结构

还是以图G所对应极大完全子图为例，存储结构示意图如下：

图10 带头结点的Nset类型空单链表

图11 图G的所有极大完全子图存储示意图。

3）程序运行结果

用邻接矩阵存储图，使用该文的算法，得到图G的所有极大完全子图{ABD，AFG，AGH，ABHI，ADEF，BCD，BHI，HIJ}。

4 结论

本文对MaxcodeFMCG（Finding Maximal Complete Subgraph by Maxcode）算法进行了研究，发现了几个有意义的性质和结论，如：性质 2，结论1，结论2，并对其进行论述或者证明，这为进一步简化算法操作奠定了理论基础。结合新的性质和结论，对算法1中矩阵合并部分的操作进行简化，简化了很多重复的操作，进一步提高了整个算法的执行效率。最后通过C语言实现了整个算法，成功的实现找出了任意图的所有极大完全子图。参考文献：

[1] 康艳荣.基于图结构挖掘算法的研究与应用[D].重庆：重庆大学，2005.

[2] Han J，Pei J，Yin Y.Ming frequent patterns without candidate generation[M].SIGMOD.2000

[3] 左孝凌，李为鉴，刘永才.离散数学[M].上海：上课科学技术文献出版社，1982：271-328.

[4] 耿国华.数据结构―用C语言描述（2011年版）[M].北京：高等教育出版社，2011：215-266.

[5] jiawei Han，Micheline Kamber. Data MiningConcepts and Techniques[M].2nd ed. morgan kaufmann publishers，2006：1-10.

[6] pang-Ning，Tan，Michael Steinbach，Vipin kumar. Introduction to Datamining. Addison Wesley，2005：146-181.

[7] Tan pang-Ning，Michael Steinbach，Vipin kumar. Introduction to Datamining[M]. Addison Wesley， 2005：146-181.

[8] 王珊，萨师煊.数据库系统概论[M].4版.北京：高等教育出版社，2007：1-39.

[9] 李伟.频繁子树挖掘研究[D].秦皇岛：燕山大学，2007.

[10] 董敏，汤建钢.求解最大完全子图的一种DNA算法[J].汉江大学学报：自然科学版，2012，44（1）：20-23.

[10] 万市场，兰绍玉.极大完全子图在管理决策中的应用[J].计算机应用，1995，15（4）：29-31.

[11] 张良均，陈俊德，刘名军，等.数据挖掘：实用案例分析[M].北京：机械工业出版社，2013：1-42.

[12] 杨仕博，贺燕琨，马志新.一种基于极大完全子图的最大频繁项集并行挖掘算法[J].微电子学与计算机，2007，24（10）：29-35.