时序网络的频繁演化模式挖掘

蒋志恒

（四川大学计算机学院，成都 610065）

0 引言

图挖掘一直是一个备受关注的问题。几乎所有的复杂系统都可以建模成动态网络，如社交网络、合作者网络、生物信息网络等，这是一种合理有效的方式。目前，在各种应用领域诸如生物信息学和医学到大型数据管理中，图结构数据的量级随着时间不断增加。有效的图挖掘算法对于增加我们对这些大型图数据集所代表的信息的理解至关重要。图挖掘的核心问题是在这些图结构的数据集中发现频繁子图。但目前大量工作的焦点集中于如何在静态图中挖掘出频繁子图，而对具有时间维度的动态网络中的频繁模式挖掘的研究较少。

信息网络通常随着时间进行演化，在此时，我们称它为动态信息网络。在一个信息网络中，一个新连接的形成、现存连接的消失或者连接属性的改变这些现象广泛存在。简单地说，对应到一个社会网络，这些现象表现为个体之间关系的建立或者解除（朋友、亲人等），或者从一种关系转变为另一种关系（朋友-＞亲人）。特别地，这些关系的建立是基于现存的关系之上，而这些关系属性的变化也是受到周围关系的影响。因此，我们不能仅仅通过考虑单个结点的变化来捕捉这样一个复杂的过程，而是应该从更大的尺度来分析这些变化。

图1 动态图的演化模式

在本文中，我们关注的就是子图是如何随着时间演化的，这种演化模式随着时间推移不断重复出现。研究这些变化对于很多场景都非常有意义，例如对社交网络趋势的分析、动态链接预测以及商品推荐。在社会网络演化的场景里，这些变化揭示了主导网络中个体信任传播、观点动态变化的复杂过程。如图1所示的一个演化模式示例，这个示例可以看作是一个信任传播过程，顾客C开始并不喜欢某个餐厅，在顾客A和顾客B先后喜欢此餐厅后，顾客C也喜欢上了餐厅，如果这种模式频繁出现，那么很显然顾客C是受到了顾客A和B的影响。

然而，现存大量研究集中于静态图的频繁模式的挖掘[1-3]，或者仅仅是将静态图中频繁模式挖掘的方式简单迁移于动态网络研究中[4-5]，并没有充分考虑到时间维度的增加为这一问题带来复杂性，无法高效地挖掘动态网络中的频繁演化模式。本文针对此问题，提出一种基于约束满足问题的多跨度频繁演化模式挖掘算法，有效地降低了算法复杂度，为频繁演化模式挖掘提供一个一般性的方法。

1 基于CSP的频繁演化模式挖掘

1.1 动态图的定义

动态图：一个图可以表示为一个元组G=(V,E,l)，其中V为一个有限的节点集，E为一个有限的边集：E⊆V×V∖{(u ,u)|u∈V}，以及边和节点标签映射 l：V∪E→label。形式地，一个动态网络是一个图的序列。并且，我们假设节点集是静态的，也就是说，对t=1,…,T，Gt=(V,Et,lt)。图Gt被称为动态图的快照。如图2所示。

图2 一个动态网络

动态网络中频繁演化模式：指不断在大图序列中重复出现的子图序列。这里所说的“出现（Occurrence）”不仅包括广度上的子图序列的存在性（即图中多个同构的子图存在相同演化模式），还包括时间维度上随着图的演替，这些子图序列在未来不断重复交叠出现。给定一个长度为T大图序列G1T=（G1,G2···,GT），其中T＞1，我们的目的是挖掘长度为k的子图序列，其中 k＞1，且子图序列满足以下约束：

（1）存在一个图序列g=(g1,g2,…,gk),∀1≤i≤k,gi是 Gj+i的子图，其中 0≤j≤T-k+1，Siisomorphism with gi，那么我们就称S1k在G1T中出现了一次。

（2）图序列在G1T中出现的次数大于一个给定的支持度阈值σ，即Support（S）≥σ。

这样的子序列我们称之为频繁子图序列。

1.2 频繁演化模式的CSP模型

在计算一个子图序列的频繁度时，我们常常需要计算出一个子图序列精确的频繁度。然而，在很多场景这并不是必要的，因为我们只需要知道哪些子图序列是频繁的，而不是准确知道。在这里，我们采用一种新型的挖掘频繁子图序列的方法，将判断一个子图序列是否频繁规约成一个约束满足问题（CSP），再对这个CSP进行求解。

约束满足问题（CSP）可以表示为一个元组(X,D,C)，在这里，X是一个变量的有续集，D是一组对应变量集中变量的域，C则是变量集X中变量之间的约束，C中所有的约束都要被满足。

（1）对每个节点v∈Vsk，集合X包含一个变量xv。

（2）D对是所有xv∈X的域的集合。每个域是的子集。

（3）集合C包含下列约束：

①对所有xv,xv'∈X，xv=xv'

②对每个变量xv∈X，l(xv)=ls(v)

③对所有xv,xv'∈X ，且

为了更清楚地说明上述标记，我们在这里用v表示子图序列中的一个节点，xv是其在CSP中对应的一个变量，这个变量的值域是大图序列中的节点。一个子图序列S1k对大图序列G1T的约束满足问题的解对应于一个子图序列S1k对大图序列G1T同构。直觉地，一个CSP的解会分配G1T中不同的节点给S1k中每个节点对应的变量，并且它们对应的节点和边的标签相匹配。一个分配有效当且仅当存在一个CSP的解对应于这个取值。

如果(X,D,C)是子图序列S1k对大图序列G1T的一个CSP，如果S1k的频繁次数满足最小支持度σ，也就是说Support(S1k)≥σ，当且仅当对X中的每个变量都至少有σ个有效的取值。如果每个变量都存在至少σ有效的取值，那么Support(S1k)≥σ，也就是说S1k是频繁的。

1.3 基于CSP的频繁演化模式挖掘

我们现在将1.2小节所述的CSP模型应用于解决频繁演化模式挖掘问题。时序网络中演化模式挖掘需要挖掘所有满足最小支持度的子图序列。因此，除了要判断一个图序列是否频繁，还要生成所有的子图序列。在这里我们采用模式增长的方法，从更小的子图通过扩展的方式得到更大的子图。

算法：FSGSequenceMining

输入：一个图序列G1T，最小支持度阈值σ，以及子图序列时间步长k

输出：所有Support(S1k)≥σ的子图序列

1 result←∅

2 fEdges表示G1T中所有的频繁的边集

3 foreach e∈fEages：

4 result←result∪SGSequenceExtension(e,G1T,σ,k,

fEdges)

5 从fEdges中移除e

6 return result

算法：SGSequenceExtension

输入：一个初始子图序列S1k，一个图序列G1T，最小支持度阈值σ，子图序列时间步长k，以及频繁边集fEdges

输出：所有的基于S1k扩展而来的频繁子图序列

1 result←S1k，candidateSet←∅

2 foreach e∈fEdges and节点u∈Vs1k：

3 i（f边e可以通过节点u扩展）：

4 ext=S1kextend e

5 i（f ext之前没有被生成）：

6 candidateSet←candidateSet∪ext

7 foreach c∈candidateSet：

8 求c对G1T的约束满足问题的解Solution

9 i（f所有变量都有至少σ个有效取值）：

10 result←result∪SGSequenceExtension

(c，G1T，σ，k，fEdges）

11 return result

如上所示，我们提供了两个算法FSGSequenceMining和SGSequenceExtension来共同实现本文算法。第一个FSGSequenceMining算法结构比较简单，提供了一个总体的挖掘算法。本文核心算法的核心由第二个算法实现。在FSGSequenceMining中，首先用频繁边集扩展初始子图序列，然后把扩展的子图序列应用约束满足问题的求解，判断这个子图序列是否频繁，然后递归调用这个算法得到所有基于初始子图S1k扩展而来的频繁子图序列。因为我们采用的是MNI的支持度计算方法，这使得一个图序列和其子图序列的支持度能够保持反单调性，即一个图序列是频繁，那么其所有的子图序列也必定是频繁的，这是本文将小的频繁子图序列扩展成更大的频繁子图序列的核心思想。

2 实验

我们使用了DBLP数据集验证了我们模型的性能，以挖掘出的子图序列数量和时间消耗作为评估指标。实验结果如图3-5。

图3 k=2时的子图序列数量（a）与运行时间（b）

图4 k=3时的子图序列数量与运行时间

图5 k=4时的子图序列数量与运行时间

图3显示子图序列时间步长k=2时的算法得到的子图序列数量和算法消耗时间都随着设置的最小支持度阈值变小。这是因为随着最小支持度阈值减少，产生大量潜在的候选子图序列，需要额外筛选这些可能频繁但实际却不频繁的子图序列。图4显示的是时间步长k=3时算法得到子图序列和算法消耗时间，同样也随着最小支持度阈值变小而减少。类似的，图5显示了k=4情况下的子图数量与时间消耗。

3 结语

很多重要的应用都要基于图挖掘，从生物信息学到社交网络的研究，从个性化广告（例如推荐系统）安全。本文介绍了一个关于大型时序网络中演化模式挖掘的算法，大型时序网络演化模式挖掘相比于传统的大图中频繁子图挖掘是一个更复杂的问题，它增加了一个时间维度，复杂度也增加了一个层次。我们将频繁演化模式建模成一个约束满足问题（CSP），减少了时序网络中演化模式挖掘问题的复杂度，为频繁演化模式挖掘提供一个一般性的方法。