Page 251 - 《软件学报》2024年第4期

李贺 等: 基于顶点组重分配的动态增量图划分算法 1829

基于改进标签传播算法的顶点组搜索策略如算法 1 所示, 算法的输入是当前的单元更新, 该单元更新涉及的
分区 P s , 以及顶点组移动增益公式 (8) 中参数 γ. 算法的输出是在单元更新附近搜索出的最有益的顶点组 VG. 这里
指出, 在搜索顶点组 VG 时要用到标签传播技术 [38,39] 的原因. 一方面标签传播算法对于发现紧密联系的一组顶点
是有效的并且拥有较低的复杂度, 紧密联系的一组顶点与本文定义的顶点组 VG 类似. 另一方面标签传播算法不
只是能用于整个图上, 最重要的是它能在局部图上并行搜索紧密联系的顶点组, 使得算法效率大大提高.
算法 1. 基于改进标签传播算法的顶点组搜索策略.

输入: partition P s , unit update, γ;
输出: vertex group (VG).
1. some boundary vertices BVS←GetBVS (P s , unit update)
2. foreach boundary vertex v ∈ BVS do
3. assign a new label to v according to formula (9)
4. end
5. repeat
6. the vertex which has label performs LPA
7. the vertex updates the label according to formula (10)
8. foreach the candidate vertex group with the same label do
W (P s )−W (VG) < (1−ε) |V|/k then
9. if
10. continue
11. end if
12. update migration_gain_array for VG
( )
13. select P t ← argmax migration_gain_array[t −1]
14. if vgm : gain s→t (VG) > 0 then
15. preserve VG
16. end if
17. end
18. until W (P s )−W (VG) < (1−ε) |V|/k for ∀VG
19. rollback to find VG with maximum migration gain
20. return VG

在算法 1 中, 首先由分区 P s 和单元更新会得到一些在动态变化附近的边界顶点, 这些边界顶点用集合 BVS 表
示 (行 1). 这里, 标签赋值和更新从 BVS 中的边界顶点开始. 初始时, 在 BVS 中的边界顶点 v 的标签为其外部邻居
的最大数目所在的分区 ID, 这可以由公式 (9) 来计算 (行 2–4).
∑
l(v) = argmax w(u), 1 ⩽ j ⩽ k and j , i (9)
j
u∈N v
其中, l(v) 表示的是边界顶点 v 的新标签, N v 表示的是顶点 v 在分区 P j 中的邻居集合. 之后, 这些边界顶点将传播
j
标签给它们所在的分区 P s 中的邻居顶点 (行 6). 由于每个顶点可能收到多个来自边界顶点的标签, 收到标签传播
信息的新的顶点将使用公式 (10) 提出的主投票规则赋值标签.
l(v) = argmax(l(v 1 ),...,l(v k )), v k ∈ UN s (10)
v
s
其中, UN 表示的是顶点 v 在其所在分区 P s 中的已更新标签的邻居集合, l(v) 表示的是其已更新邻居所拥有的最
v
大数量的标签. 这里指出, 当收到标签传播信息的顶点已经被赋值了一个标签, 那么同样利用公式 (10) 提出的主
投票规则更新其标签 (行 7). 顶点组 VG 通过不断加入与其相连并且有着相同标签的新的顶点进行扩展. 对于每一