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

1.图挖掘的主要目标

答：挖掘频繁子结构是图集合中非常基本的模式。频繁子结构可以刻画集合的特征，区分不同的组群体，对图进行分类和聚类，构造图索引和更方便地在图数据库中进行相似性搜索。

频繁图的基本定义：图g的顶点集合用V（g）表示，边集合用E（g）表示。标号函数L将顶点或边映射到标号。图g是另一个图G的子图，如果存在从图g到图G的子图同构。给定一个标记的图数据集D={G1，G2，G3，... ... ，Gn}，图g的支持度support（g）或者频度frequency（g）定义为g作为子图在D中出现的百分比或者次数。频繁图是支持度不小于最小支持度阈值min_sup的图。

发现频繁子结构的步骤通常有两个：1、产生频繁子结构的候选；2、检查每个候选的频度。大多数的频繁子结构发现的研究都集中在第一步的优化，因为第二步包含子图同构检验，计算复杂度相当高。目前有两种基本方法：Apriori方法和模式增长方法。Apriori方法频繁子结构挖掘算法的频繁图搜索开始于小规模图，按照自底向上的方式产生具有附加顶点、变或路径的候选图。图规模的定义依赖于使用的算法。根据自底向上的策略的选择，也产生了具体的算法，分为顶点、边、边不相交路径的具体实施策略。Apriori方法是基于图的广度优先搜索进行的。模式增长方法比Apriori方法更加灵活，可以根据实际需要采用图的广度优先搜索或者深度优先搜索。模式增长方法是选择以边为增长策略的，也是自底向上增长策略进行，它对每次增长的边用从增长原点到新增长边的顶点序列记录，然后对附加完成增长边的子图计算频繁度，考察新增长的边对频繁度的影响程度，记录频度，选取频度最高的增长边加入频繁子结构中，依次迭代此过程，直至频度小于或等于边界条件。

以上发现频繁子结构的图是无向图的发现方法，对于有约束条件的图需要加入约束条件，例如权值、有向等。

2.社会网络分析

答：社会网络是由图来表示的异构多关系数据集。 社会网络的研究主要集中在分析节点的度，即每个节点相关联的边数，节点对之间的距离，用最短路径长度度量。网络直径是节点对之间的最大距离。其他节点到节点的距离包括节点对之间的平均距离和有效直径。社会网络是一种动态变化的网络，可能呈现出稠化幂律、收缩直径、重尾出度和入度分布等特征。

由于社会网络组成的数据对象是异构的、多关系的和半结构化，所以链接挖掘是社会网络数据挖掘的主要领域。考察节点之间关系的权重，然后按照权重进行降值排列是社会网络某个时刻的数据挖掘分析。对两个有先后关系的时刻进行分析，可以分析两个时刻之间社会网络的变化，得出关系变化的结果。

转载地址：http://fqpdi.baihongyu.com/