Page 253 - 《软件学报》2024年第4期
P. 253
李贺 等: 基于顶点组重分配的动态增量图划分算法 1831
12. if vgm : gain s→t (VG) > 0 then
13. migrate VG to P t
14. end if
15. end for
16. return P ′
3.4 算法时空复杂度分析
ED-IDGP 算法首先需要利用动态处理器处理单元更新, 同样由于其简单但有效性, 这部分的时间复杂度可忽
略不计. 对于 ED-IDGP 算法, 它的时间复杂度主要由基于改进标签传播算法的顶点组搜索策略的时间复杂度决
定. 因为在基于改进标签传播算法的顶点组搜索策略中, 它不仅完成了顶点组搜索的过程, 而且也完成了找出拥有
最大移动增益的顶点组 VG. 在顶点组搜索过程中, ED-IDGP 算法从单元更新附近的边界顶点开始, 利用标签传播
的原理从而获得一系列的候选顶点组 VG. 因此, 改进标签传播至多需要 O(|P s |) 的时间复杂度. 事实上, 由于负载
平衡的约束, 顶点组搜索的时间复杂度远远要小于 O(|P s |). 因此, 对于每一个单元更新, ED-IDGP 算法的时间复杂
度为 O(|P s |). 对于所有的动态变化∆G, 在 ED-IDGP 算法中, 我们使用了一种分布式流的方式将∆G 分给 k 个动态
处理器分别做处理, 所以其时间复杂度为 O((|∆G|/k)×|P s |).
ED-IDGP 算法的空间复杂度主要由两方面决定, 一是在顶点组搜索过程中需要保留一些候选顶点组, 二是数
组 migration_gain_array. ED-IDGP 算法需要额外的内存空间记录顶点组 VG 移动到其他分区 P j 的移动增益值, 这
里 1 ⩽ j ⩽ k 并且 j , i . 数组 migration_gain_array 被用来存储这部分的数据, 其所需要的内存空间大小为 O(k). 此
外, 我们需要在单元更新附近搜索顶点组 VG 的过程中保留那些移动增益大于 0 的候选顶点组, 这也需要一个额
外的内存空间存储, 我们用 O(|PVG|) 标记这部分的内存空间, 它是一个很小的值. 因此, ED-IDGP 算法的空间复杂
度为 O(k+|PVG|).
Streaming 算法 [18] 采用一个评分函数来处理每一个单元更新, 每个分数的计算是一个常数时间的操作. 因此,
对于所有的动态变化中, 如果我们同样采用分布式流的方式将∆G 分给 k 个动态处理器分别做处理, Streaming 算
法的时间复杂度为 O((|∆G|/k)×k). Streaming 算法的空间复杂度只包括 k 个分区的评分. 因此, Streaming 算法的空
间复杂度为 O(k). 可以看到, Streaming 算法的时空复杂度都相对较小, 因为其只是把动态变化部分加入图中, 并没
有对更新后的图进行进一步的划分以保证图的划分质量, 所以 Streaming 算法的划分质量相对较差.
4 实验分析
4.1 实验环境与数据集
本文主要使用真实图对 IDGP 算法和 ED-IDGP 算法的效果和性能进行评估和分析, 表 2 总结了实验用到的
6 个真实图 [40,41] . 在这些真实图中, RoadNet-PA 是一个道路网络, DBLP 是一个 Web 网络, 其他是社交网络.
RoadNet-PA 服从均匀分布, 其他服从幂律分布. 为了模拟动态环境, 我们将原始数据集随机分为两部分, 一部分作
为初始图 G, 将被划分为 k 个分区, 而另外一部分作为动态变化∆G. 对于所有的图, 我们生成由大小|∆G|控制的随
机单元更新. 例如, 将图分为 70% 和 30%, 将 70% 那部分作为初始图进行划分, 将 30% 那部分作为动态变化部分.
由于初始图和动态变化的选择总体上是随机的, 因此会遵循一些动态变化规律以确保图的属性不会发生显著的变
化. 例如, 动态更新导致直径更小并且平均度更高, 仅有很少的高度顶点会在动态更新过程中出现, 大量的高度顶
点已经在初始图 G 中存在. 实验选择 Streaming 算法 [18] 获得初始图 G 的一个划分 P. 我们在一台内存大小为 32 GB,
并且处理器的配置为 Intel(R) Core(TM) i7-4790@3.60 GHz 的机器上执行所有的实验.
实验中, 我们选择单元素增量图划分方法 CCP [37] 、批处理增量图划分方法 IncKGGGP [28] 、流式图划分方法
Streaming [18] 作为比较方法, 与本文提出的 IDGP 算法和 ED-IDGP 算法做对比.
(1) 单元素增量图划分算法 CCP 为顶点或边的插入或删除分别提出了划分策略, 满足实时图的划分. 但是
CCP 算法在处理动态变化时假设新顶点的大部分邻居信息是可用的, 具有一定的局限性. 此外, CCP 算法在做优
化时仅考虑移动单个顶点.
