缪杨帆

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

0 引言

现实世界中的网络多为无标度网络[1]，即在网络数据中，少量的节点存在大量的邻居节点，大量的节点仅有少量的邻居节点，也就是说节点的度分布[2]符合幂率特性[3]。如科研合作者网络便是较为典型的无标度网络，少量的作者会有大量的与之相关联的其他作者，而大部分作者仅有少数的几个合作者。又如微博关注关系所形成的网络，少数人拥有大量的粉丝，如明星、企业家，等等，而作为普通人基本上只有少量的关注者。正是现实生活中的这种现象形成了符合幂率特性的网络，也就形成了团或者社区[4]。

现实生活中大多数人的活动范围都有一定的限定，这种限定并非人为创造的，而是自然而然形成的。正是基于这种现象，本文假定用户在网络数据图中所做的查询基本上会在社区范围内。也就是说，将网络抽象为图结构，用户所查询的子图大多数时候会在某些特定的区域范围内。

一个社区一般都会存在一个或者多个度较大的节点。本文提出的基于启发式策略的图分割[5]算法正是基于此，通过从一个度较大的节点开始，基于节点之间的相似性度量，不断地试图去激活邻居节点，然后再由邻居节点去激活其自身的邻居节点，直到完成分区。后续的子图匹配[6]操作将在各个分区之内同时进行，可以极大的提高子图匹配的效率。

1 节点相似性度量

1.1 节点相似性

定义1.1（结构性等价）对于一个给定的网络图G=(V ，E )，对于任意的 vk∈V ，满足 vi≠vk且 vj≠vk，如果e(vi，vk)∈E ，当且仅当 e(vj，vk)∈E ，则称 vi与 vj是结构性等价的。

图1 结构性等价

如图1所示，节点1和节点3是结构性等价的，因为节点1和节点2、节点4相邻，而节点3同样和节点2、节点4相邻，因此称节点1和节点3为结构性等价。同样，在图1中节点5和节点6也是结构性等价的。

然而在现实世界的应用中，因为结构性等价太多严格，因此一些相对松散的等价定义被提出，如自同构等价和规则性等价[7]等，不过由于这些定义没有相应的扩展方法，因此本文采用了一些简化的相似性度量方法。

1.2 节点相似性度量

节点相似性度量方法主要包括Jaccard[8]相似性度量和Cosine[9]相似性度量方法。

对于给定的网络图，对于图中的节点vi和vj，其相似性定义如下：

（1）Jaccard定义

在上面两个等式中，其中Ni表示节点vi的邻域，Nj表示节点vj的邻域，|*|表示元素的个数。其相似性度量值在0-1之间。

但是，根据如上定义，存在两个相邻节点之间相似性为0的情况。例如在图1中，N7={8 ，9，5，6} ，N9={7}，而N7∩N9=∅，虽然从结构性等价角度讲合理，但是两个节点相连接，相似性的可能同样存在。一般的修正方法是在计算Nv时，将节点v算在内，即N7={7 ，8，9，5，6} ，N9={7 ，9} 。

然而，以上两种标准的基于相似性度量的方法需要计算每一对节点之间的相似性，故其时间复杂度为O(n2)。当n较大时，计算相似性的时间将急剧增大，故不适合较大的数据图。因此本文并未采用上述定义，而是重新定义了度量标准。

给定网络图结构，假设节点vi和节点vj为网络图中的两个节点，且节点vi和节点vj直接相连，假设已知节点vi属于分区Ⅱ，那么节点vj属于分区Ⅱ的概率，也即节点vi能够激活节点vj的概率为：

其中，其中Nij表示节点vi与节点vj共同邻居，之所以加1，主要考虑到节点vi和节点vj直接相连的情况，dj表示节点vj自身的度。

依旧以图1为例进行说明。N54={4} ，d4=4 ，假设节点5属于分区Ⅱ，那么节点4同样属于分区Ⅱ的概率，也即节点5激活节点4的概率为：

2 图分割

分割图时有两种方法，一种是将分区之间的边切割掉，另一种是将分区之间的边保留下来。由于在大规模的子图匹配过程中需要考虑到内存及时间效率的问题，因此本文采用的HSGSA算法是将边直接切割。分割过程如图2所示。

图2 HSGSA分割过程

假定用户设定的阈值p=0.5，开始时选定的度最大的节点为4，周围邻居节点集合N4={3 ，5，7，8} ，以节点5为例，节点4和节点5的共同邻居节点集合为N45={7} ，d5=3，根据公式（1）计算得出 p(4 ，5) ≥0.5 ，故节点5被激活，与节点4属于相同的分区，以同样的方式计算其他节点，可知如图步骤②所示，节点5，7，8可被激活，而节点3无法被激活，接着从激活的节点开始继续相同的过程，激活节点6。接着找度最大的节点，假定找到节点3，如图步骤③所示，然后以上述同样的方式激活节点1，2，如图步骤④所示，并最终形成两个分区。

算法过程如下：

算法1：基于启发式策略的图分割算法

输入：数据图G=（V，E），激活的阈值p

输出：分割后的数据图

算法：

获取数据图G中度最大的顶点v_max;

将顶点v_max加入队列Q，将顶点v_max加入分区n;

While队列Q非空then

移出Q队首元素v;

获取顶点v的邻居顶点N_v;

For n_v in N_v

If顶点n_v所属分区为空then

If（（|N_nv|+1）/d_v）>=p then

将顶点n_v加入队列Q，同时将其

加入分区n;

End if

Else

将顶点n_v和v边加入新分区，修改顶

点度;

End if

删除边，修改顶点v和n_v的度;

End for

End While

首先从网络数据图中找到度最大的节点v，将其加入到分区中。然后遍历这个节点的每一个邻居节点，首先判断该节点是否已经被划分到某一个分区内，如果没有，那么接着判断该邻居顶点能否被v激活，即根据公式判断其概率是否大于用户给定的值p，大于的话将该邻居节点加入节点v所属的团内，删除边，同时修改相关节点的度，如果邻居节点已经被划分到某一个团内，则将边加入社区，然后删除边，修改相关节点的度，如果概率小于用户给定的p值，则直接删除边即可，如此循环直到遍历完所有的邻居节点，形成一个分区。若要形成多个分区重复上述步骤即可。

3.1 实验数据

实验数据主要来自科研合作者网络数据（DBLP）。因本文提出的算法的适用条件为符合幂率分布的网络数据图，故首先从DBLP数据集中抽取出五个数据图，如表 1 所示，在对 G1，G2，G3，G4，G5 的度分布进行验证之后确定所抽取的数据图其度分布均符合幂率特性。

3.2 实验分析

3 实验及结果分析

首先在DBLP数据集中取G1数据图，将其分成两个分区。图3是随着p值变化，分割出来的分区占原来数据图的比例，以及HSGSA算法中边的丢失率。从图3中可以看出，当p的取值逐渐增大时，新形成的分区规模逐渐减小，而边的丢失率也在减少。但是，当p值较大时会形成大量的小分区，而这对图匹配有重大的影响，既不能形成大量的小分区，又不能造成大量的边丢失。故p的取值既不能太大也不能太小。如果要形成多个分区p的值应当设置的偏大，而本文提出的分割算法旨在能够快速分割，又能自由控制分区的个数，因此p的值设置在0.2-0.4之间比较好。

表1 数据图

图3 数据图G1中p值变化带来的影响

在以下实验过程中设定p的值均为0.3，分成两个分区。从算法的描述部分可知，本文设计的基于启发式策略的图分割算法对切割的边不作保存，虽然会造成一些边的缺失，但是所需要的内存空间就相对较小，在大规模的图处理过程中可以减少设备的内存消耗。与此同时，分割的时间也会随着数据图规模的增加而呈现线性增长，分割时间也随分区个数的增加而逐渐增加，如图4所示。

图4中的④是将数据图分割成两个分区后，结果匹配的展示，蓝色表示的为随机生成的23个查询子图，红色表示的为HSGSA算法形成的两个分区匹配出的结果数，从结果中可以看出虽然匹配效果并没有完全正确，但实验中的查询子图是通过随机算法生成的，而本文设计的算法则是在假定用户查询不是随机的，而是在分区范围内的，故在符合假设的条件下准确率会提高。这也说明了本文提出的先将大规模数据图分割成几个部分，同时进行匹配的合理性。

图4 实验结果

4 结语

基于现实网络基本上符合幂律分布的特性，在假定用户的大多查询模式处于社区范围内的情况下，本文提出了基于启发式策略的图分割算法，一方面确保能够对大规模数据图按指定的分区数进行分割，同时又能够使其分割时间随数据图的规模成线性增长。而且从实验结果中可以发现，在对图进行分割时去掉分区之间的边依然能够取得较好的匹配效果，而对于内存空间和时间的消耗却不多。