伴随着数字经济的蓬勃发展，移动互联网、智能终端越发普及，社交网络、智慧交通和生命科学等领域涌现出海量数据^[1]. 这些数据规模大，数据元素间关联关系复杂，业界称为图大数据，简称大图. 以全球最大的社交平台Facebook为例，其社交网络拥有超过20亿用户和上千亿条好友关系. 传统的单机由于性能有限，难以从大图中快速挖掘蕴藏的价值，需要拥有强大计算与存储能力的并行计算系统作为支撑. 为充分利用并行计算系统开展大图并行处理，首先要对大图实施划分.

图划分，是指按照某种策略将大图划分为若干个满足一定约束条件的子图. 子图规模均衡性和子图割边数量，是影响大图分布式并行处理性能和效率的重要因素^[2]，主要体现在：规模越均衡、割边数越少，映射到各计算节点的负载越均衡、节点间通信代价越低、处理效率越高. 如何获取均衡性好、割边数少的图划分结果，已成为业界关注重点^[3-4]. 国内外学者提出许多图划分算法，主要有离线划分、分布式划分和流式划分. 离线划分算法在实施划分前，将大图全部加载到内存，典型代表有谱划分算法^[5]和Metis划分算法^[6]. 这类图划分算法依据图全局信息实现高质量划分，但时间复杂度高且受内存大小限制，常用于划分小规模图数据. 伴随着图数据规模的持续增大，分布式划分和流式划分逐渐成为研究热点^[7-8]. 其中，分布式划分算法充分利用并行计算系统中多个处理节点的算力和存储资源，依据图全局信息实施划分，如ParMetis划分算法^[9]. 流式划分算法采用边加载边划分的策略，不依赖图全局信息，具有时间复杂度低的特点，典型代表有LDG^[10]，FENNEL^[11]，HeiStream^[12]. 该类图划分算法通常采用单加载器-单划分器结构，存在性能瓶颈，且由于缺乏图全局信息，存在冷启动问题，即在划分初始阶段，划分器的部分顶点因缺乏划分决策信息，难以获取最优子图位置编号，导致划分质量不理想. 如图1所示，采用LDG启发式规则将大图划分为2个子图，假设按照顺序加载，且每个子图中最大顶点数为4，将得到划分结果1（有4条割边），但实际最优结果应为划分结果2（有2条割边）. 之所以出现偏差，主要因为该启发式规则并未充分利用高度数顶点等图数据流中的有价值信息.

图  1  图划分冷启动问题

Figure  1.  Cold start problem of graph partitioning

下载: 全尺寸图片 幻灯片

针对上述问题，本文提出一种带缓冲区的分布式流式划分算法. 该算法采用多加载-多划分器架构，各加载器以顶点为单位、按照特定顺序并行加载图数据；各划分器维护一个缓存，对相应加载器输出的图顶点流数据先缓存，然后按顶点度数重新排序，并依据不同划分目标实施划分. 在充分利用缓冲区辅助信息提高划分质量的同时，借助分布式流式机制提高划分算法性能. 为进一步提高划分质量，我们借助重流机制对划分结果进行微调优化. 本文的创新点及贡献如下：

1）设计一种多加载器-多划分器的分布式图划分架构. 通过多个加载器和多划分器分别并行读取和划分图数据，提高图数据的加载效率和划分效率，缓解传统流式划分算法存在的性能瓶颈.

2）提出一种分布式图数据缓冲机制. 每个划分器维护一个缓冲区，采用快速排序算法对缓冲区内图数据按照顶点度数由高到低排序，优先将高度数顶点作为“种子”实施划分，有效缓解冷启动问题.

3）设计4条流式启发式规则. 分别以最优均衡性、简单高效原则、最大化模块度兼顾均衡性、最小化割边比兼顾均衡性为目标，将大图划分为一系列小规模子图，可以满足不同应用场景下的划分需求.

4）在真实的分布式系统中开展一系列实验，全面检验所提算法划分真实大图与合成大图的划分质量和划分性能.

1.   相关工作

图划分算法主要包括3类：离线划分、流式划分和分布式划分. 谱划分^[5]是典型的离线划分算法，它首先计算相似矩阵的拉普拉斯矩阵，然后求出其第2大特征值及其对应的特征向量，对图进行递归二分. 该算法对很多类型的图数据都能生成高质量划分结果. Metis^[6]采用多级$k$路划分策略，将图划分为3个阶段：1）第1阶段通常借助收缩匹配或聚簇等策略来构建输入图的连续粗略近似，组成层次化结构；2）一旦图只剩下少数几个顶点，第2阶段借助常用的离线图划分算法直接将其划分为$k$个子图；3）第3阶段将该划分结果连续投影到层次结构中的更精细级别，并使用局部搜索算法对划分结果进行细化. 与谱划分类似，Metis^[6]计算开销较大，不便用来划分大规模图数据. 例如，Tsourakakis等人^[13]采用Metis对拥有超过14亿条边的Twitter图进行划分，其划分总时长超过8.5h.

流式划分方面，Stanton等人^[10]首次将流模型引入到图划分，并提出包含LDG在内的10条流式启发式规则，在数据由磁盘加载到内存的一次性过程中，仅利用图局部信息即可实施划分. Tsourakakis等人^[13]在文献[10]的基础上，定义一个融合LDG和Folklore^[14]2种启发式规则的流式划分框架FENNEL，将顶点分配到具有更多邻居的子图. Nishimura等人^[11]提出重流思想，并设计了LDG和FENNEL的重流版本，它们保持图划分目标函数不变，并以上一轮流式划分的结果作为本轮的初始划分，对划分结果不断微调优化，主要适用于相同或相近的大图持续出现的场景. Awadelkarim等人^[15]研究顶点顺序对流式划分质量的影响，根据特定优先级对流式加载的顶点进行静态或动态排序，并提出LDG的优先级版本reLDG. Patwary等人^[16]提出基于贪心策略的流式划分算法，设计含有数百个顶点的滑动窗口，为候选顶点提供更多辅助信息. 类似地，Faraj等人^[17]提出带缓冲区的流式划分算法，首先构建代表批处理顶点和已划分顶点的结构模型图，再利用传统多级图划分算法完成划分. Zeng等人^[18]提出非均衡流式划分算法，可按照任意比例关系流式地将大图划分为一系列子图. Sun等人^[19]将博弈理论与流式划分相结合，采用多人博弈纳什均衡，实现各个时间窗口内流数据的最优划分. 这些流式划分算法均采用单加载器-单划分器架构，容易出现性能瓶颈. 此外，Özsu等人^[20]、Abbas等人^[21]关注流式划分算法的性能评测问题.

分布式划分方面，许多学者基于多级图划分范式设计了划分算法，如基于共享内存的KaMinPar^[22]，Mt-KaHIP^[23]和基于分布式内存的ParMetis^[9]，ParHIP^[24]等. 其中，KaMinPar^[22]进一步将多级算法延伸到初始划分阶段，结合递归二分和直接$k$路划分计算初始划分方案. Mt-KaHIP^[23]将多级图划分算法与KaHIP图划分工具相结合，旨在提供适用于大规模图数据的高质量图划分解决方案. ParMetis^[9]是Metis^[6]的并行扩展版本，专门用于处理大规模图数据的划分和排序问题，旨在优化分布式内存体系结构上的性能. ParHIP^[24]是一种用于超图划分的并行算法，同时支持共享内存和分布式内存计算环境. 总的来说，基于共享内存的分布式划分算法^[22-23]可实现较高的划分质量和合理的可扩展性，但基于分布式内存的分布式划分算法^[9]划分质量依然不高，且可扩展性低、难以保证划分均衡性. 此外，Battaglino等人^[25]则积极尝试并行化流式划分算法，在FENNEL算法的基础上提出了分布式流式划分算法Grasp，这是当前性能最好的分布式划分算法.

上述划分算法^{[10,13,15-17,19,24-25]}均属于割边划分，还有部分算法专注于割点划分^[26-29]，这类算法用连接边流替代顶点流作为输入，目标通常是最小化割点数. 尽管从应用角度来看，它们与本文研究工作密切相关，但该类问题并不是本文工作的重点. 更多有关图划分工作请参考文献[30].

2.   图划分概念

2.1   划分问题形式化描述

图划分按照某种方式将大图$G$切割成多个小的子图${G_i}\left( {i \in \left[ {1,{\text{2}},…,k} \right]} \right)$，即$G = {G_1} \cup {G_2} \cup…\cup {G_k}$. 设大图$G = \left( {V,E} \right)$, 其中$V = \left\{ {{v_1},{v_2},…,{v_n}} \right\}$，$E = \left\{ {{e_{ij}}|{v_i},{v_j} \in V} \right\}$分别代表其顶点集和连接边集，$n$为顶点数. $\forall {v_j} \in V$，将与其关联的连接边条数称为度数，记为$deg\left( {{v_j}} \right)$；与${v_j}$有连接边相连的顶点集合称为邻居，记为$N\left( {{v_j}} \right) = \left\{ {{v_k}|{v_k} \in V \wedge {e_{jk}} \in E} \right\}$，则有$deg\left( {{v_j}} \right) = \left| N\left( {{v_j}} \right) = \left\{ {v_k} \in V \wedge {e_{jk}} \in E \right\} \right|$.$\forall i \in \left[ {1,{\text{2}},…,k} \right]$,即${G_i} = \left( {{V_i},{E_i}} \right)$是$G$一个子图，并满足${V_i} \subseteq V$和${E_i} \subseteq E$. 这些子图集合${\pi _k} = \left\{ {{G_1},{G_2},…,{G_k}} \right\}$为$G$的一个$k$路划分，当且仅当${\forall _{i,j}} \in \left[ {1,k} \right]$，$i \ne j$，均有${V_i} \cap {V_j} = \emptyset$‌，$V = \mathop \cup \limits_{i = 1}^k {V_i}$，$E = \mathop \cup \limits_{i = 1}^k {E_i}$，横跨2个子图${G_i}$和${G_j}$的连接边称为割边，割边集记为$E\left( {{G_i},{G_j}} \right)$.

图划分问题就是：给定大图$G$，寻找它的一个$k$路划分$\pi _k^ * = \left\{ {G_1^ * ,G_2^ * ,…,G_k^ * } \right\}$，使得对于$k$路划分空间$\Omega$中的任一划分${\pi _k}$，在保证各子图顶点数均衡的前提下，割边数最少. 该问题可形式化描述为式（1）和式（2）：

其中主要符号及其含义如表1所示：

表  1  符号及含义

Table  1.  Symble and Meaning

符号	含义
$G$，${G_i}$，$G_i^\tau$	图、子图和时刻$\tau$的子图
$V$和$E$	顶点集和边集
$v$和$e$	某个顶点和某条边
$N\left( v \right)$	顶点$v$的邻居集
${\pi _k}$和$\pi _k^\tau$	$k$路划分和时刻$\tau$的$k$路划分
$E\left( {{G_i},{G_j}} \right)$	割边集
${m_i}$和${b_i}$	计算节点及其缓冲区

下载: 导出CSV 

| 显示表格

2.2   划分评价标准

不同划分算法的划分质量参差不齐. 这里采用业界常用的划分质量评价指标构建了评价体系，主要包括：

1）均衡性$\rho = \mathop {\max }\limits_{i \in \left[ {1,k} \right]} \left( {{{\left| {{V_i}} \right|} \mathord{\left/ {\vphantom {{\left| {{V_i}} \right|} {{{\left| V \right|} \mathord{\left/ {\vphantom {{\left| V \right|} k}} \right. } k}}}} \right. } {{{\left| V \right|} \mathord{\left/ {\vphantom {{\left| V \right|} k}} \right. } k}}}} \right)$，用来度量子图顶点数与理想情况下每个子图应拥有的顶点数的偏离程度. 偏离理想值1.0越大，意味着并行处理阶段各节点间负载越不均衡，处理时间越长；

2）割边比$\lambda = \dfrac{{\left| {\mathop \cup \limits_{i = 1,j = 1}^k E\left( {{G_i},{G_j}} \right)} \right|}}{{\left| E \right|}}$，用来度量划分${\pi _k}$的割边数占总边数的比例，$\lambda$值越大，并行处理阶段各处理节点间的通信开销越大，处理时间越长.

3）划分总时间$\tau = \mathop {\max }\limits_{i \in \left[ {i,k} \right]} \left( {{\tau _{i,{\mathrm{ld}}}} + {\tau _{i,{\mathrm{part}}}}} \right)$. 其中，$\tau_{i,\mathrm{ld}}$和$\tau_{i,\mathrm{part}}$分别表示第$i \in \left[ {1,k} \right]$个划分进程的数据加载时间和划分时间. 对于采用单加载器-单划分器的流式划分算法以及离线图划分算法而言，其划分总时间$\tau = {\tau _{{\mathrm{ld}}}} + {\tau _{{\mathrm{part}}}}$. ${\tau _{{\mathrm{ld}}}}$和${\tau _{{\mathrm{part}}}}$分别表示数据加载时间和划分时间.

4）效率$\varepsilon=\dfrac{\tau_{\mathrm{seq}}}{proc\times\tau_{\mathrm{par}}}$. 其中，$\tau\mathrm{_{seq}}$和$\tau_{\mathrm{par}}$分别表示划分进程数$proc = 1$和$proc \gt 1$时的划分总时间.$\varepsilon$用来表征图数据规模不变的情况下，划分总时间随划分进程数增加的变化情况. $\varepsilon$值越接近于1.0，表示效率越高，即并行计算资源有效利用率越高.

3.   带缓冲区的分布式流式划分算法

3.1   算法整体流程

流式划分算法中普遍存在冷启动问题. 为缓解该问题，本节提出带缓冲区的分布式流式划分算法. 具体工作流程如图2所示.

图  2  带缓冲区的分布式流式图划分算法流程

Figure  2.  Algorithm flow of distributed buffered streaming graph partitioning

下载: 全尺寸图片 幻灯片

该算法采用多加载器-多划分器架构，运行于分布式系统的不同处理节点上. 不妨设分布式系统由$k$个同构计算节点组成，节点间通过高速通信链路连接，记所有节点集合为$M = \left\{ {{m_1},{m_2},…,{m_k}} \right\}$. 其中，每个计算节点上运行1对加载器-划分器，加载器负责从分布式文件系统中读取大图$G = \left( {V,E} \right)$，并传递给随后的划分器，因而共有$k$对加载器-划分器. 每个划分器维护一个大小为$w$的缓冲区，用以存放图数据流. 每个划分器都保存一份划分决策信息$\pi _k^\tau$，即时刻$\tau$大图$G$的$k$路划分.

$k$个加载器按照随机原则，以顶点为单位从文件系统中成批并行读取$w$个图顶点，并发送给相应划分器；划分器首先缓存收到的图数据流，待缓冲区满后，利用快速排序算法对缓冲区内的图顶点按照度数由高到底排序；随后根据所提4条启发式规则BH（buffered hashing），BB（buffered balance），BWM（buffered weighted modularity），Hybrid（3.2节中介绍）中的某一条，计算缓冲区内各个顶点应放置到右侧分布式系统的哪个处理节点上并实施放置；重复上述过程$ceil\left( {{n \mathord{\left/ {\vphantom {n w}} \right. } w}} \right)$批次，直至数据加载完毕时，$G$被划分为$k$个子图. 其中，$ceil\left( * \right)$表示向上取整函数，$n$为$G$的顶点数. 最后，将已有划分方案作为已知信息，采用重流方式，对划分方案微调以提高划分质量. 具体算法如算法1所示：

算法 1. DBSGP（distributed buffered streaming graph partitioning）.

输入：$G$，$k$，${b_i}$，$w$；

输出：$\pi _k^\tau$.

① 初始化批次数num_batches为$ceil\left( {{n \mathord{\left/ {\vphantom {n w}} \right. } w}} \right)$；

② 初始化各计算节点${p_i}$缓冲区${b_i}$为空集$\varphi$；

③ 初始化时间$\tau$为0;初始化重流次数num_streams；

④ 初始化$k$路划分$\pi _k^\tau$为空；

⑤ 重流大图$G$执行num_streams次，每次各加载器 并行执行以下操作：BWM或Hybrid启发式规则；

⑥ 循环开始

⑦ 以$w$为单位加载图数据num_batches批次，每 个批次执行以下操作：

⑧ 循环开始

⑨ 将加载的$w$个顶点放置到缓冲区${b_i}$中；

⑩ 各划分器并行执行以下操作：

⑪ 并行开始

⑫ 用快排算法对缓冲区${b_i}$中的顶点按照度数非 递增排序；

⑬ 对缓冲区${b_i}$中的每个顶点，执行以下操作：

⑭ 根据启发式规则计算它应放置的子图编号$j$， 并完成放置；

⑮ 并行结束

⑯ 各划分器同步各个子图的最新状态$\pi _k^\tau$，并更 新时间$\tau$为$\tau + w$；

⑰ 循环结束

⑱ 循环结束

不妨设$\pi _k^\tau = \left\{ {G_1^\tau ,G_2^\tau ,…,G_k^\tau } \right\}$为时刻$\tau$大图$G$的$k$路划分. 其中$G_i^\tau \left( {i \in \left[ {1,k} \right]} \right)$表示时刻$\tau$子图${G_i}$的状态. 每个划分器${p_i}\left( {i \in 1,k} \right)$所维护的缓冲区${b_i}\left( {i \in 1,k} \right)$中存放已按度数由高到低有序排列的顶点，记为$\left\{ {v_{i1}^\tau ,v_{i2}^\tau ,…,v_{iw}^\tau } \right\}$. 时刻$\tau + 1$，划分器${p_i}\left( {i \in 1,k} \right)$基于当前的划分决策信息$\pi _k^\tau$，按照某种启发式规则，决定缓冲区${b_i}$中某个顶点$v$应“流”向哪个子图. 待缓冲区内所有顶点分配完毕，各划分器同步更新$\pi _k^\tau$. 若出现多个划分器同时更新某一子图$G_k^\tau$的状态，则按照划分器编号由小到大的顺序按序更新. 重复上述过程直至所有顶点加载完毕，即可得到$G$的$k$路划分${\pi _k}$. 将${\pi _k}$作为已知信息，对图数据$G = \left( {V,E} \right)$实施重流，利用支持重流的启发式规则进一步优化${\pi _k}$.

3.2   分布式流式启发式规则

本节设计了4条分布式流式启发式规则，分别对应一个算法. 各个划分器并行执行，用以确定各自缓冲区中当前顶点$v$应放置的子图编号$ind$.

1）BH：按照简单高效原则实施划分，尽可能提高划分效率. 设计哈希函数$H:{B_i} \to \left\{ {1,{\text{2}},…,k} \right\}$，将缓冲区中最新的顶点${v_{\mathrm{g}}}$分配给子图$ind$：

本文取$H\left( {{v_{\mathrm{g}}}} \right) = {v_{\mathrm{g}}}\text{mod} k$.

2）BB：按照最优均衡性目标实施划分. 在时刻$\tau$，将缓冲区中最新的顶点${v_{\mathrm{g}}}$“流”向当前已分配顶点数最少的子图$G_i^\tau$. 若存在多个具有最少顶点数的子图，则随机指派${v_{\mathrm{g}}}$到其中任一子图：

BH和BB启发式规则不便利用上一次流式划分的结果来指导当前流中顶点的划分，因而重流效果不明显.

3）BWH：在兼顾最优均衡性原则的同时，按照最大化子图模块度目标实施划分. 在时刻$t$，将缓冲区中最新的顶点${v_{\mathrm{g}}}$“流”向某个子图，使得：①${v_{\mathrm{g}}}$的邻居顶点集与子图$G_i^\tau$顶点集交集阶数最大；②添加惩罚函数项以惩罚顶点数多的子图，从而避免失衡. 若2个或多个子图的模块度相等，则随机指派${v_{\mathrm{g}}}$到其中任一子图：

其中$\phi \left( {V_i^\tau } \right) = 1 - \alpha {\left| {V_i^\tau } \right|^\gamma }$. 通过合理地选择$\alpha$和$\gamma$，来控制$\phi \left( {V_i^\tau } \right)$在整个函数中所占的比重. 在重流时，将上一次流式划分的结果（记为${\pi _k} = \left\{ {{G_1},{G_2},…,{G_k}} \right\}$）作为已知信息，按照如下公式计算缓冲区中最新的顶点${v_{\mathrm{g}}}$应“流”向的子图编号：

其中${V_i}$表示上一次流式划分结果中第$i\left( {i \in \left[ {1,k} \right]} \right)$个子图${G_i}$的顶点集；$V_i^\tau$表示子图${G_i}$在本次流式划分中时刻$\tau$的状态.

4）Hybrid：在兼顾最优均衡性原则的同时，按照最小化割边比目标实施划分. 给定一种区分顶点度数高低的算法，如设定一个合理的阈值$\eta$，在时刻$\tau$，对度数超过该阈值的顶点采用BH决定其“流”向哪个子图；否则采用BWM：

Hybrid规则的重流版本与式（7）的唯一区别是当$deg\left( {{v_{\mathrm{g}}}} \right) \gt \eta$时，调用重流版的BWM即式（6）.

4.   实验结果与分析

4.1   实验环境

实验数据. 我们从SNAP^[31]中搜集了wiki-Talk，LiveJournal，Friendster这3个真实数据集，详见表2.

表  2  真实大图信息

Table  2.  Information of Real-World Big Graph

数据集	顶点数	边数	顶点平均度数	数据集类型
wiki-Talk	2 394 385	5 021 410	4.2	维基百科网络
LiveJournal	4 847 571	68 993 773	28.5	社交网络
Friendster	65 608 366	1 806 067 135	55.1	社交网络

下载: 导出CSV 

| 显示表格

此外，我们还利用图合成工具PaRMAT^[32]合成了一系列不同规模、顶点度数分布均服从幂率分布的图数据集，详见表3.

表  3  合成大图信息

Table  3.  Information of Composite Big Graph

尺度参数	顶点数/M	边数/B	顶点平均度数
26	67	1.07	32
27	134	2.14	32
28	268	4.29	32
29	537	8.58	32
30	1 070	17.1	32
注：B表示10亿.

下载: 导出CSV 

| 显示表格

对比基准. 选择当前离线划分质量最好的KaMinPar^[22]和在线划分质量最好的HeiStream^[12]，Grasp^[25]作为对比基准. 其中，KaMinPar^[22]是一种基于共享内存的深层多级图划分算法，除粗化阶段外，在初始划分阶段继续采用多级算法利用递归二分和直接$k$路划分计算初始划分方案. HeiStream^[12]是一种单加载器-单划分器的缓冲流式划分算法，它按批接收顶点并缓存在缓冲区中，联合批次中的节点和已存在的划分结构构建待划分的图，再利用多级图划分算法实施划分. Grasp^[25]是一个采用MPI实现的分布式流式划分算法，其划分规则是Fennel. 通过使用调整的划分参数对分布式图进行重新流式处理，以实现对大图的快速$k$路划分.

分布式系统运行在一个由2台DELL Precision 7920 塔式工作站通过网线直接连接而成的工作站机群. 其中，每台工作站都配有2颗英特尔至强金牌6254@3.1GHz CPU、512GB主存和1TB SSD、8TB HDD. 操作系统版本是Centos 7.9.2009，编译器版本是GCC 9.3，MPI版本是MPICH-3.4.3.

4.2   结果分析

本节设计3组实验，分别讨论所提算法的划分质量与性能. 第1组实验考查划分真实图和合成图的划分质量，评价指标包括均衡性$\rho$、割边比$\lambda$；第2组实验考查划分合成图的性能，评价指标包括划分总时间$\tau$和效率$\varepsilon$. 第3组实验考查缓冲区大小对划分质量的影响，评价指标包括均衡性$\rho$、割边比$\lambda$和划分总时间$\tau$. 在每组实验中，取BWM的参数$\alpha$和$\gamma$分别为$\left\lceil {{n \mathord{\left/ {\vphantom {n k}} \right. } k}} \right\rceil$和1，其中$n$表示图顶点数，$k$表示划分路数；取Hybrid的参数$\eta$为所划分数据集的平均顶点度数；取重流次数为5；每种算法均取5次实验的平均值作为最终结果.

划分质量实验：本实验主要目的是考查所提算法中4条流式启发式规则BH，BB，BWM，Hybrid对2个真实图和6个合成图的划分质量. 不妨取划分进程数$proc = 8$、划分路数$k = 8$、缓冲区大小$\omega = 1\;024$，均衡性和割边比实验结果分别见图3、图4和表4.

图  3  不同划分算法划分均衡性对比

Figure  3.  Partition equalization comparison of different partitioning algorithms

下载: 全尺寸图片 幻灯片

图  4  不同划分算法划分割边比对比

Figure  4.  Partitioning cut edge ratio comparison of different partitioning algorithms

下载: 全尺寸图片 幻灯片

表  4  不同划分算法的划分质量对比

Table  4.  Partition Quality Comparison of Different Partitioning Algorithms

数据集	KaMinPar			HeiStream			Grasp			BH（本文）			BB（本文）			BWM（本文）			Hybrid（本文）
	$\rho$	$\lambda$		$\rho$	$\lambda$		$\rho$	$\lambda$		$\rho$	$\lambda$		$\rho$	$\lambda$		$\rho$	$\lambda$		$\rho$	$\lambda$
wiki-Talk	1.030	0.293		1.030	0.561		4.986	0.397		2.293	0.343		2.320	0.332		2.247	0.193		2.342	0.187
LiveJournal	1.030	0.088		1.030	0.251		4.534	0.203		2.353	0.187		2.353	0.154		2.398	0.011		2.369	0.009
Friendster	1.030	0.256		1.030	0.317		4.489	0.251		2.336	0.232		2.331	0.217		2.347	0.182		2.381	0.177
RMAT-26	1.030	0.788		1.030	0.610		4.412	0.551		1.923	0.450		1.919	0.423		1.930	0.352		1.919	0.347
RMAT-27	1.030	0.789		1.030	0.596		4.284	0.494		1.890	0.440		1.883	0.412		1.898	0.361		1.876	0.332
RMAT-28	1.030	0.787		1.030	0.586		4.158	0.476		1.769	0.417		1.763	0.403		1.770	0.344		1.769	0.318
RMAT-29	1.030	0.789		1.030	0.574		4.007	0.421		1.745	0.422		1.742	0.409		1.742	0.352		1.727	0.342
RMAT-30	1.030	0.790		1.030	0.569		3.913	0.496		1.706	0.411		1.701	0.397		1.709	0.341		1.715	0.336
注：$\rho$和$\lambda$分别表示均衡性和割边比. KaMinPar和HeiStream均取非均衡因子$\varepsilon = 0.03$.

下载: 导出CSV 

| 显示表格

不难看出，无论真实图还是合成图，所提算法4条启发式规则BH，BB，BWM，Hybrid的划分质量均明显优于当前最好的在线划分算法Grasp和HeiStream，但在均衡性指标上逊色于当前最好的离线划分算法KaMinPar.

具体来讲，以Hybrid启发式规则为例，割边比指标$\lambda$较KaMinPar缩减至少36.2%（wiki-Talk数据集），较HeiStream和Grasp分别缩减至少40.4%和18.8%（RMAT-29数据集）；以BH为例，其均衡性指标$\rho$较KaMinPar和HeiStream均增加128.4%（LiveJournal数据集），而Grasp的均衡性相较于KaMinPar和HeiStream均增加358.3%. 但也应看到KaMinPar和HeiStream为保证均衡性，付出了高昂的时间代价. 此外，BH和BB在均衡性指标$\rho$优于BWM和Hybrid，但在割边比指标$\lambda$方面却劣于BWM和Hybrid. 这是因为前两者侧重于均衡性，而后两者追求最小化割边比.

由此可见，与不使用缓冲区的Grasp算法相比，本文提出缓冲区机制能够明显提高划分质量，有效缓解冷启动问题. 而使用缓冲区的HeiStream算法表现之所以较本文算法存在一定差距，是因为它将每个已划分子图“池化”一个超级顶点，与缓冲区中各顶点构造一张图，再利用传统多级图划分算法对其实施划分. 该“池化”操作造成划分决策信息损失较大，降低了划分质量.

划分性能实验：本实验主要目的是测试所提4条流式启发式规则BH，BB，BWM，Hybrid的划分性能. 不妨固定图数据为RMAT-22、缓冲区大小$\omega = 1\,\;024$、划分路数$k = 128$，调整划分进程数$proc \in \{ 1,2,4,8,16, 32,64,128 \}$, 记录不同划分算法的总划分时间. 实验结果见图5、图6、图7、表5和表6所示.

图  5  不同划分算法划分总时间对比

Figure  5.  Total time comparison for partitioning of different partitioning algorithms

下载: 全尺寸图片 幻灯片

图  6  不同划分算法效率对比

Figure  6.  Efficiency comparison of different partitioning algorithms

下载: 全尺寸图片 幻灯片

图  7  不同划分算法的数据加载时间占总划分总时间比例

Figure  7.  Proportion of data loading time in total partitioning time of different partitioning algorithms

下载: 全尺寸图片 幻灯片

表  5  不同划分算法划分性能对比

Table  5.  Partition Performance of Different Partitioning Algorithms

$k$	KaMinPar			HeiStream			Grasp			BH（本文）			BB（本文）			BWM（本文）			Hybrid（本文）
	$\tau$	$\varepsilon$		$\tau$	$\varepsilon$		$\tau$	$\varepsilon$		$\tau$	$\varepsilon$		$\tau$	$\varepsilon$		$\tau$	$\varepsilon$		$\tau$	$\varepsilon$
1	50.431	/		19.175	/		19.941	/		17.621	/		21.104	/		23.054	/		23.453	/
2	58.156	0.338		21.975	0.934		10.525	0.663		11.420	0.641		12.737	0.644		13.776	0.669		13.658	0.669
4	66.688	0.167		25.418	0.250		6.884	0.669		7.974	0.658		7.741	0.653		8.597	0.681		8.386	0.681
8	65.703	0.090		8.981	0.115		5.510	0.369		6.223	0.362		5.958	0.352		6.569	0.362		6.460	0.362
16	55.226	0.047		8.872	0.057		4.403	0.209		5.196	0.202		5.518	0.204		5.732	0.211		5.356	0.211
32	50.826	0.028		9.735	0.029		3.779	0.106		4.571	0.105		4.571	0.103		4.968	0.104		4.855	0.104
64	80.996	0.012		17.813	0.014		6.051	0.041		7.152	0.039		7.066	0.039		7.353	0.042		7.159	0.042
128	253.41	0.001		310.58	0.005		281.08	0.005		283.05	0.005		288.04	0.005		289.23	0.005		291.11	0.005

下载: 导出CSV 

| 显示表格

表  6  不同划分算法的数据加载时间占总划分总时间比例

Table  6.  Proportion of Data Loading Time in Total Partitioning Time of Different Partitioning Algorithms

$k$	HeiStream			Grasp			BH（本文）			BB（本文）			BWM（本文）			Hybrid（本文）
	${\tau _{ld}}$	${{{\tau _{ld}}} \mathord{\left/ {\vphantom {{{\tau _{ld}}} \tau }} \right. } \tau }$		${\tau _{ld}}$	${{{\tau _{ld}}} \mathord{\left/ {\vphantom {{{\tau _{ld}}} \tau }} \right. } \tau }$		${\tau _{ld}}$	${{{\tau _{ld}}} \mathord{\left/ {\vphantom {{{\tau _{ld}}} \tau }} \right. } \tau }$		${\tau _{ld}}$	${{{\tau _{ld}}} \mathord{\left/ {\vphantom {{{\tau _{ld}}} \tau }} \right. } \tau }$		${\tau _{ld}}$	${{{\tau _{ld}}} \mathord{\left/ {\vphantom {{{\tau _{ld}}} \tau }} \right. } \tau }$		${\tau _{ld}}$	${{{\tau _{ld}}} \mathord{\left/ {\vphantom {{{\tau _{ld}}} \tau }} \right. } \tau }$
1	6.833	0.356		3.921	0.196		3.465	0.196		4.171	0.197		4.831	0.209		4.628	0.219
2	7.517	0.342		2.084	0.198		2.233	0.195		2.506	0.196		2.753	0.199		2.664	0.209
4	7.671	0.301		1.365	0.198		1.557	0.195		1.508	0.194		1.708	0.198		1.665	0.215
8	2.668	0.297		1.074	0.194		1.227	0.197		1.184	0.198		1.284	0.195		1.277	0.214
16	2.618	0.295		0.870	0.197		1.025	0.197		1.041	0.188		1.175	0.204		1.046	0.189
32	2.640	0.271		0.753	0.199		0.910	0.199		0.910	0.199		0.996	0.200		0.957	0.209
64	5.232	0.293		1.188	0.196		1.401	0.195		1.401	0.198		1.451	0.197		1.423	0.201
128	7.972	0.025		56.106	0.199		57.252	0.202		58.379	0.202		59.113	0.204		59.005	0.204

下载: 导出CSV 

| 显示表格

从图5、图6和表5可以看出，当划分进程数$1 \lt proc \lt 128$时，所提算法4条启发式规则BH，BB，BWM，Hybrid在划分总时间指标$\tau$上显著优于当前最好的离线划分算法KaMinPar和当前最好的在线划分算法Grasp.

具体来讲，不妨以表现最好的BH为例，较KaMinPar缩减至少80.4%（对应$proc = 2$）；较HeiStream和Grasp分别缩减至少30.7%和12.9%（对应$proc = 8$）. 当$proc = 1$时，Grasp和所提4条流式启发式规则均蜕化成单加载器-单划分器架构划分算法，它们的划分总时间与HeiStream的差异不明显. 当$proc = 128$时，此时进程数已超过CPU物理核心数（80），引发严重的计算资源争用，导致所有划分算法的划分总时间都显著增加. 在效率指标$\varepsilon$上，无论$proc$如何变化，所提4条启发式规则与Grasp表现接近，且均显著优于KaMinPar和HeiStream（$proc = 2$除外）. 之所以BH，BB，BWM，Hybrid的效率随着划分进程数$proc$的增加先升高，当$proc = 4$时效率最高（并行计算资源得到充分利用），而当$proc$进一步增加时，效率迅速降低，主要是因为并行划分带来的收益不足以弥补并行开销.

从图7和表6可以看出，当划分进程数$proc \lt 128$时，所提划分算法的平均划分时间比采用单加载器-单划分器架构的HeiStream算法的划分时间缩减29.8%.

具体来看，HeiStream流式划分算法的数据加载时间占划分总时间的比例平均为30.8%，最高达到35.6%. 而本文所提算法采用多加载器-多划分器架构，其数据加载时间占划分总时间的比例平均为20.1%，最高仅为21.9%. 这表明多加载器-多划分器架构能够有效缓解传统流式划分算法存在的性能瓶颈.

缓冲区大小影响力实验：本实验主要目的是测试缓冲区大小对所提算法划分质量和性能的影响. 不妨以LiveJournal图数据为例，固定划分进程数$proc = 8$，调整划分窗口$\omega \in \left\{128，256，512，1024，2048\right\}$，记录不同划分算法的划分质量和划分总时间，实验结果见表7.

表  7  不同缓冲区大小对划分质量和性能的影响

Table  7.  Impact of Buffer Zone Size on Partitioning Quality and Performance

$\omega$	BH（本文）				BB（本文）				BWM（本文）				Hybrid（本文）
	$\rho$	$\lambda$	$\tau$		$\rho$	$\lambda$	$\tau$		$\rho$	$\lambda$	$\tau$		$\rho$	$\lambda$	$\tau$
128	2.369	0.182	3.039		2.375	0.151	2.818		2.421	0.010	2.901		2.358	0.009	2.896
256	2.347	0.187	2.974		2.353	0.156	2.810		2.398	0.011	2.891		2.347	0.009	2.845
512	2.347	0.187	2.813		2.347	0.157	2.796		2.392	0.011	2.844		2.336	0.010	2.841
1024	2.347	0.187	2.793		2.352	0.154	2.792		2.398	0.011	2.805		2.370	0.009	2.802
2048	2.347	0.187	2.840		2.347	0.157	2.780		2.387	0.012	2.803		2.336	0.011	2.798

下载: 导出CSV 

| 显示表格

可以看出，所提算法4条启发式规则BH，BB，BWM，Hybrid在不同缓冲区下划分质量变化并不明显，但划分总时间随着缓冲区$\omega$的增加先降低后提高，当$\omega = 1\,\;024$时，划分总时间最短. 这是因为当滑动窗口过小时，需要频繁从磁盘中读取图数据流，I/O开销较大. 当$\omega$进一步增加时，划分总时间逐渐增加，可能的原因是缓冲区顶点排序操作时间增大.

总体来说，如表8所示，在4条启发式规则中，BH和BB更侧重于划分的均衡性，适用于实时性要求高、负载均衡敏感、通信开销不敏感的图计算场景；而BWM和Hybrid兼顾了划分的均衡性和割边比，适用于实时性要求低、负载均衡和通信开销敏感的图计算场景.

表  8  不同启发式规则的优缺点以及适用场景

Table  8.  Advantages and Disadvantages and Application Scenarios of Different Heuristics

特性	BH（本文）	BB（本文）	BWM（本文）	Hybrid（本文）
优点	简单高效	划分均衡性好	划分模块度高、均衡性好	拓扑结构感知、划分割边比低、均衡性好
缺点	划分割边比高	划分割边比高	计算复杂	计算复杂
适用场景	实时性要求高、负载均衡敏感、 通信开销不敏感的图计算场景	实时性要求高、负载均衡敏感、 通信开销不敏感的图计算场景	实时性要求低、负载均衡和 通信开销敏感的图计算场景	实时性要求低、负载均衡和 通信开销敏感的图计算场景

下载: 导出CSV 

| 显示表格

5.   结　　论

本文针对现有图划分算法在划分大图时存在的划分质量和效率难以平衡的问题，提出一种带缓冲区的分布式流式划分算法，通过结合带缓冲区的流式划分算法与分布式划分算法两者的优势，在利用缓冲区辅助信息提高划分质量的同时，借助多加载器-多划分器架构的分布式流式机制提高划分算法性能. 此外，为满足不同划分场景需求，我们设计了4条启发式规则，分别按照最优均衡性、简单高效原则、最大化模块度兼顾均衡性、最小化割边比兼顾均衡性实施划分. 多节点分布式系统上的划分质量与性能实验表明：本文所提算法的划分质量（割边比）比当前最好的在线划分算法改善至少18.8%；多加载器-多划分器架构的设计将图数据加载时间占划分总时间的比例，从单加载器-单划分器架构流式划分算法的平均30.8%降低至平均20.1%，缓解了单加载器-单划分器划分算法存在的性能瓶颈；分布式缓冲机制通过优先划分高度数顶点，有效缓解了冷启动问题.

作者贡献声明：史惠康提出了算法思路和实验方案；王泽胜、胡克坤、董刚负责完成实验并撰写论文；赵有健提出指导意见并修改论文.