本文共 2044 字，大约阅读时间需要 6 分钟。

1. 子图模式：将关联分析方法应用到复杂实体、文档数据的建模，运用到图形表示
2. 频繁子图挖掘：在图的集合中发现一组公共子结构
3. 图与子图：图是一种表示实体集之间联系的数据结构，由顶点集和连接顶点对的边集组成；当一个图的顶点集是另一个图的子集且其边集也是这个图的子集，那么前者是后者的子图；顶点vi是顶点的序列，而给每个顶点vi赋予一个标号l（vi）代表实体；每条边（vi,vj）也可以给予一个边标号l（vi,vj），描述实体间的联系，所以顶点标号和边标号可以在一个图中出现多次
4. 图之间的支持度：子图g的支持度=包含它的所有图的个数/所有图集群的个数
5. 频繁子图挖掘：给定图的集合和支持度阈值，找出所有使得s（g）>=minsup的子图g；主要关注无向连通图（在一个图中，点和边可以重复）：
   1. 如果图中的每对顶点之间都存在一条路径，路径是序列中每对相邻顶点（vi，v（i+1））之间都有一条的边，则为连通图（这应该是至少原则，至少前后两个顶点之间有一条边）
   2. （vi，vj）和（vj，vi）无区别则这个边是无向的，一个图只包含无向边则为无向图
6. 候选子图的个数很大：
   1. 某个顶点标号可能在一个图中出现多次，且边也可以
   2. 相同的顶点标号对可以有多条边标号选择
   3. 这是因为图是二维模型，在事务图中，点和边是集合的形式出现的，所以候选的图可以随意组合，并且都是可以重复的
7. 类Apriori方法：
   1. 数据变换：将图变换为类似于事务的形式，一边及其两个顶点组合映射为一个项，事务的宽度由图的边数决定；但问题是仅当图中的每一个边标号和其顶点标号的组合是唯一的才可行
   2. 频繁子图挖掘算法的一般结构：
      1. 候选产生：合并频繁（k-1）-子图对，得到候选k-子图
      2. 候选剪枝：丢弃包含非频繁的（k-1）-子图的所有候选k-子图
      3. 支持度计数：统计图的集群中包含每个候选的图的个数
      4. 候选删除：丢弃支持度<minsup的所有候选子图
8. 候选产生：如何定义子图的大小k（k可以是顶点个数或者边数），通过添加一个顶点，迭代的扩展子图的方法为顶点增长；或者添加一条边到已有的子图中来扩展子图为边增长；为了避免产生重复的候选，两个（k-1）-子图必须共享一个共同的（k-2）-子图，后者被称为核
   1. 通过顶点增长产生候选：图的邻接矩阵表示：矩阵的每一项（i，j）为连接顶点vi和vj的边标号或者0（对角线对称矩阵）；顶点增长方法可以看做合并一对（k-1）*（k-1）的邻接矩阵产生k*k邻接矩阵：
      1. 如果删除两个邻接矩阵的最后一行和最后一列得到的子矩阵相同的话，两个邻接矩阵可以合并
      2. 结果是在第一个矩阵上添加第二个矩阵的最后一行和最后一列；新矩阵的对角线为0，其余项可以为0或者用连接顶点对的合法的边标号替换
      3. 结果图必原来的第一个图多一条边（新的边标号为0）或者两条边，新的边标号未知，从而大大增加了候选子图的个数
   2. 通过边增长产生候选：将一个新的边插入到一个已经存在的频繁子图中，而结果子图中顶点也可能不会增加；仅当第一个图删除一条边得到的子图与第二个图删除一条边得到的子图，拓扑等价，这两个图才能合并，合并后，结果是第一个图添加第二个图的那条额外的边
      1. 顶点拓扑等价：如果一条新边分别附着在两个点上，且图一样，那么这两个顶点互相拓扑等价；作为（k-1）-子图时，当两个顶点拓扑等价时，即为相等，当核外边的点的顶点标号相等时，也即为相等
      2. 频繁子图合并产生候选子图时，当顶点相同时，两个图的顶点可以合并也可以不合并，不同时就不能合并（当然合并后完全相同时，只是产生了第三个完全相同的复制，并不是合并的图了）
   3. 当与一对（k-1）-子图相关联的核有多个时，还可能产生多个候选子图；边增长策略产生的候选子图的数量趋向于<顶点增长策略产生的
9. 候选剪枝：产生候选k-子图后，要剪去（k-1）-子图非频繁的候选，相继从k-子图删除一条边（意思是一次删除一条，总共有k个子图要检测），检验对应的（k-1）-子图是否连通（对，就是上面的那种连通）且频繁，若不是直接丢弃k-候选子图；为了检查（k-1）-子图是否频繁，需要将它和其他频繁（k-1）-子图匹配，判定两个图是否拓扑等价称为图同构问题：
   1. 处理图同构：将每个图都映射到一个唯一的串表达式，即代码或规范标号，规范标号有如下的性质：如果两个图是同构的，则它们的代码是相同的；实际步骤：
      1. 找出每个图的邻接矩阵表示；为了导出一个图的所有邻接矩阵，需要考虑矩阵行和对应列的所有可能的排列
      2. 确定每个邻接矩阵的串表示：通过逐列连接矩阵的上三角元素得到的，code=
      3. 比较图的所有串表达式，找出最大或最小的字典次序值的串
      4. 当然这方法开销大；还有其他方法，如存放先前计算的规范标号或通过加入顶点标号和顶点度数等附加信息来减少确定规范标号所需要的排列数
10. 支持度计数：快速的方法：建立和维护一个与每个频繁（k-1）-子图相关联的图ID表，如果新的候选子图由一对频繁（k-1）-子图合并而成，对它们的对应图ID表求交集，而子图的同构检测在表中的图上进行

转载地址：https://blog.csdn.net/u013103305/article/details/83317806 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！