时燕++张玉琢

摘要：在计算机领域中，图是最复杂的数据结构之一。该文研究了图的挖掘理论及算法。特别针对参考文献[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 （邻接矩……