一种基于GN算法的动态图划分方法*

罗晓霞，王 佳，罗香玉，李嘉楠

(西安科技大学计算机科学与技术学院，陕西 西安 710054)

1 引言

图已经被广泛应用于医疗、食品、环保、气象和生物等各个领域[1,2]。在现实世界中，图在不断地演化，例如社交网络中[3]，新成员的加入、新关系的建立、成员之间联系频率的变化，这些都会引起图的演化。并且随着图数据规模的急剧增长，单台计算机已无法对其进行处理，因此分布式图计算平台日益流行[4,5]。对动态图数据进行高效的划分处理，是提高分布式图计算效率的有效手段。

通过对图划分方法的深入研究发现，目前的一些算法主要是针对静态图划分的研究[6,7]。Hash划分、面向BSP(Bulk Synchronous Parallel)模型的负载均衡Hash图数据划分BHP(Balanced Hash Partition)、Range划分、基于平衡标签传播的图划分BLP (Balanced Label propagation for Partitioning)等，这类算法适用于图结构稳定、不发生变化和不需要实时响应的静态图。当处理随时间动态演化的图时，研究人员大多采用流式划分方法。Stanton等人[8]考虑了各种启发式方法来将图顶点分配给处理器节点，并且必须在图顶点添加到图分区系统时进行划分。Tsourakakis等人[9]提出可扩展的流图划分框架FENNEL，通过重新设计目标函数来考虑传统平衡图分区问题的硬约束以及切边成本。Nishimura等人[10]将流式划分的过程变为迭代过程，图的顶点能够重新分配给处理器节点。骆融臻[11]设计并实现了一个能够可靠使用的分布式流式图划分系统，每个子分类器通过全局的共享状态进行同步，但存在较高的通信延迟。张梦琳[12]针对动态图结构，提出了一种有向性动态维护策略，通过判断图更新操作是否涉及边界顶点而给出不同的逻辑移动策略。李茜锦[13]提出一种流图分割方法，解决了有向图流分割过程中的信息丢失问题。Lü等人[14]基于优先级的调度算法为重要顶点指定较高的优先级，以进行有效的处理，可以缩短收敛时间。以上关于动态图划分的研究，将顶点的当前邻居信息作为划分依据，并没有考虑将来一段时间内顶点邻居信息的变化。当已划分的顶点邻居信息发生变化时，需要对这些顶点进行转移，这将会带来较大的顶点转移开销，降低图划分质量。

为了解决该问题，本文提出了一种基于GN(Girvan and Newman)算法[15]的动态图划分方法。考虑到未来一段时间内顶点邻居信息的变化，先收集一段时间内的若干个顶点邻居信息变化操作，利用GN算法对新加入的顶点进行预划分；然后将预划分产生的社区结果插入到当前分区中，完成动态图的划分。

2 图划分的相关理论

2.1 GN算法

GN算法是一种社区发现算法，本质是基于聚类的分裂思想，使用边介数作为相似度的度量方法,边介数是指图中任意2个顶点通过此边的最短路径的数目。GN算法步骤如下所示：

首先计算图中所有边的边介数；然后找到边介数最大的边并将它从图中移除，计算此时的模块度；接下来重新计算图中剩下的边介数；重复上述步骤，直到图中所有的边都被删除，每个顶点单独成为一个社区为止。因为GN算法不能判断算法的终止位置，所以Newman引入了模块度的概念，用来衡量社区的划分是不是相对比较好的结果，比较每次划分之后的模块度，将模块度最大的划分结果作为最终社区划分结果。模块度计算公式如(1)所示：

(1)

其中，c表示图中的一个社区；C为所有社区的集合；m表示图中的总边数；lc表示社区c中所有内部边的条数；Dc表示社区c中所有顶点的度之和。

使用GN算法可以较好地发现网络中存在的社区结构，该算法对存在孤立顶点的网络、全连接社区、无权图和高内聚网络等特殊形式，均表现出良好的鲁棒性。

2.2 图划分评价指标

图划分结果主要有2个评价指标：负载均衡度和交叉边数[16]。其中，负载均衡度是指图数据应该尽可能均衡地被划分到多台计算机进行处理，以充分发挥分布式计算的性能优势。交叉边是指一条边的2个顶点被分配在不同的子图中，交叉边数会直接影响分布式计算时网络的通信开销[17]。

负载均衡度L是用各分区所含顶点数的方差来衡量，其计算公式如(2)所示:

(2)

其中，p表示分区的总个数；px表示第x个分区中的顶点个数，1≤x≤p；A表示图中总顶点数与分区个数的比值，即每个分区中的平均顶点数。

交叉边数是将各个子图之间的交叉边相加得到的结果，减少交叉边数可提高各分区之间的通信效率。

3 基于GN算法的动态图划分方法

3.1 基本思想

动态图的划分问题可以描述如下：假设在t时刻，存在一个动态图Gt(Vt，Et)，其中，Vt和Et分别表示图Gt的顶点集和边集，P={Pt1,Pt2,Pt3,…,Ptx}表示t时刻的初始划分。经过Δt时间之后，收集给定数量N的图更新操作，求取新的划分P′，同时保持较好的负载均衡度和交叉边数。

本文方法的基本思想是：将收集到的N个图更新操作进行分类处理，对于所有的顶点插入操作，首先用GN算法进行预划分，之后将预划分结果插入当前分区中；其余的顶点删除、边插入/删除操作，分别根据收集的信息依次更新。本文方法的核心是基于GN算法，GN算法计算边介数需要找到所有最短路径，其时间复杂度为O(m*n)，总时间复杂度为O(m2*n)，所以本文方法的总时间复杂度在m条边和n个顶点的图中为O(m2*n)。

3.2 相关定义

定义1图更新操作GUOPT(Graph Update Operation)：给定图G，对该图进行的每一次更新叫做一个图更新操作，可以通过〈type,value〉的形式表示。type∈{1,2,3,4}，1表示插入顶点操作，2表示删除顶点操作，3表示插入边操作，4表示删除边操作；value表示具体更新的顶点或者边的信息。

(1) 插入顶点操作：用〈1,value〉表示，value=i，i是图G中新插入的顶点。

(2) 删除顶点操作：用〈2,value〉表示，value=j，j是图G中要删除的顶点。

(3) 插入边操作：用〈3,value〉表示，value=(u,v)，u和v都是图G中的顶点，表示在顶点u和v之间插入一条边.

(4) 删除边操作：用〈4,value〉表示，value=(u,v)，u和v都是图G中的顶点，表示删除顶点u和v之间的边。

例如，〈1,2〉表示插入顶点2；〈2,1〉表示删除顶点1；〈3,(2,3)〉表示在顶点2和顶点3之间添加一条边；〈4,(1,3)〉表示删除顶点1和顶点3之间的边。

定义2图更新操作集GUOPTS(Graph Update Operation Set)：由一段时间内发生的图更新操作组成，包含多个GUOPT操作，可以表示为：GUOPTS={GUOPT1,GUOPT2,GUOPT3,…,GUOPTy}，其中y表示第y个图更新操作。

定义3图更新操作总次数：在动态图演化过程中，出现的所有图更新操作次数的总和。

定义4图更新频度：使用基于GN算法的动态图划分方法对整个动态图进行划分所需要的划分次数。当给定的图更新操作集大小为N时，更新频度M的计算公式如(3)所示：

(3)

3.3 基本步骤

以给定规模的图更新操作集GUOPTS为划分单位，收集若干个连续的图更新操作之后，做出划分决策。基于GN算法的动态图划分方法基本步骤如下所示：

步骤1根据式(3)计算动态图划分所需要的图更新频度M。

步骤2收集连续的N个图更新操作，组成图更新操作集GUOPTS。

步骤3对于插入顶点操作，用GN算法对GUOPTS进行处理，将新插入顶点所构成的子图预划分，产生若干个独立的社区，然后按照边的插入和删除以及顶点的删除操作进行更新：

对于插入顶点操作，可以用〈1,i〉表示，使用GN算法对新增顶点进行预划分，得到多个社区，社区内部联系紧密，社区之间联系稀疏。对于插入边操作，可以用〈3,(u,v)〉来表示，分为2种情况：当顶点u和顶点v同属于当前图或新增图时，将(u,v)插入当前图或新增图中；当2个顶点中一个属于当前图，而另一个属于新增图时，将该边记为当前图与新增图的交叉边。对于删除边操作，可以用〈4,(u,v)〉来表示，分为2种情况：当顶点u和顶点v同属于当前图或新增图时，将(u,v)从当前图或新增图中删除；当2顶点中一个属于当前图，而另一个属于新增图时，将该边从当前图与新增图的交叉边中删除。对于删除顶点操作，可以用〈2,j〉来表示，j是图中任意顶点的编号，无论该顶点属于当前图或新增图，在对应的点集合中删除该点的信息。

步骤4计算预划分产生的每个社区与各个当前分区之间的交叉边数，将各社区分别插入到与之交叉边数最多的当前分区中。

将预划分产生的社区结果插入到当前分区的具体步骤如下所示：首先，将预划分产生的每个社区结果与各个当前分区之间的交叉边数置为0；然后，从第一个社区开始循环，遍历每一条连接该社区某个顶点与当前分区某个顶点的边，每次都将对应当前分区关联的交叉边计数值加1，直到所有社区交叉边计数结束；最后，比较每个社区与所有当前分区的交叉边计数值，找出最大值，将社区插入到最大的交叉边计数值对应的当前分区中。

步骤5根据更新频度M判断有无未处理的操作，若有，转到步骤2；否则结束。

该方法的基本流程如图1所示。

Figure 1 Basic process of dynamic graph partition图1 动态图划分的基本流程

4 实验与结果分析

4.1 数据集与实验环境

实验的数据集是来自斯坦福大学SNAP(Stanford Network Analysis Project)项目组公开图数据集中的CollegeMsg和Soc-sign-bitcoin-otc，具如表1所示。

Table 1 Data sets

数据集CollegeMsg是由加州大学欧文分校的在线社交网络上发送的私人消息组成，用户可以在网络中搜索其他人，然后根据个人资料信息发起对话，边(e,f,t)表示用户e在t时刻向用户f发送了一条私人消息。数据集Soc-sign-bitcoin-otc是一个在Bitcoin OTC平台进行比特币交易的评价网络，边(e,f,t)表示用户e在t时刻对用户f进行了信用评价。由于图的演化是一个平稳的过程，针对动态图的划分，将上述2个数据集分别按1∶5的比例分为2部分，用少量数据作为当前图，用大量数据作为图的更新。

实验运行环境是Windows 10，CPU配置是Intel(R) Core(TM) i5-4460，内存配置是8 GB。基于Python 3.7实现本文提出的方法与传统的流式划分方法。

4.2 实验及结果分析

本实验分为图更新操作集大小N的确定与图划分质量对比2个阶段。

第1阶段：为了分析图更新操作集的大小N对划分质量的影响，N分别取1 000,2 000,3 000,4 000,5 000和6 000进行实验，使用第3节方法完成对整个CollegeMsg的划分。实验结果如图2和图3所示。

Figure 2 Load balance results图2 负载均衡度结果

Figure 3 Crossed edges results图3 交叉边数结果

由图2和图3可得，随着图更新操作集大小N取值的增大，各分区所含顶点数方差和交叉边数的值越来越小，曲线斜率也越来越小，由此说明，图划分质量越来越好，但图更新的实时性不断地在损失。当N=4000时，图划分质量和实时性最佳。在实际应用中，应该权衡划分质量和更新实时性2个方面来确定合适的图更新操作集大小N。

第2阶段：分别使用传统流式划分方法和本文方法对动态图进行划分，比较划分之后的负载均衡度和交叉边数的大小。根据第1阶段的实验结果，给定图更新操作集的大小N=4000，由式(3)计算可得，完成数据集CollegeMsg的划分所需要的更新频度为13，完成数据集Soc-sign-bitcoin-otc的划分需要的更新频度为8。对数据集CollegeMsg的划分负载均衡度对比和交叉边数对比分别如图4和图5所示，对数据集Soc-sign-bitcoin-otc的划分负载均衡度对比和交叉边数对比分别如图6和图7所示。

Figure 4 Comparison of load balance (CollegeMsg)图4 负载均衡度对比图(CollegeMsg)

Figure 5 Comparison of crossed edges(CollegeMsg)图5 交叉边数对比图(CollegeMsg)

Figure 6 Comparison of load balance (Soc-sign-bitcoin-otc)图6 负载均衡度对比图(Soc-sign-bitcoin-otc)

Figure 7 Comparison of crossed edges(Soc-sign-bitcoin-otc)图7 交叉边数对比图(Soc-sign-bitcoin-otc)

由图4和图6可知，当经过相同的图更新频度M时，本文方法的负载均衡度曲线明显低于传统的流式划分方法的；由图5和图7可知，当经过相同的图更新频度M时，本文方法的交叉边数曲线明显低于传统的流式划分方法的。由此可见，本文方法的划分结果质量明显优于流式划分方法的，各分区负载更加均衡，且产生的交叉边数更少。此外，随着图更新频度M的增加，本文方法的优越性更加明显，最终在完成整个图划分时，相比流式划分方法，本文方法对数据集CollegeMsg的划分结果中交叉边数减小了13%，负载均衡度减少了42.3%，本文方法对数据集Soc-sign-bitcoin-otc的划分结果中交叉边数减少了25.4%，负载均衡度减少了6%。

5 结束语

对图数据进行合理划分，是进行分布式图计算和分析的基础和前提。目前针对静态图的划分研究已经比较成熟，为了进一步提高动态图的划分质量，本文提出了基于GN算法的动态图划分方法，对图更新操作集内的新增图进行社区划分，再将新增图以社区为单位划分至与之联系紧密的当前分区中。实验结果表明，相较于传统流式划分方法，该方法可显著地提高动态图的划分质量。未来还需要进一步研究图更新操作集大小N的取值对划分结果的影响。