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

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

载平衡, 将新顶点分配到拥有最低负载大小的分区中. 其二是某个时刻新顶点插入时, 有关于该顶点的一条边信息
随之插入, 为简单起见, 将该新顶点和这条边分配到其边的另一个端点所在的分区中. 这里指出, 对于该新顶点的
其他边, 在下一时刻, 会将其作为新边对待, 后面会具体介绍对应的划分策略.
● 边插入. 在增量图划分中, 每一条边插入需要在负载平衡的基础上最小化边切割的数量. 对于新边的插入可
分为两种情况. 第 1 种情况是新边的两个端点在同一分区, 因为本文研究的是基于边割的图划分问题, 所以对于这
种情况直接将该条边分配到端点所在的分区中. 第 2 种情况是新边的两个端点在不同的分区中, 如果直接将该条
边分配到现有的划分中, 那么会导致边切割的数量增加 1. 对于这种情况, 给定一条新边 (v i , v j ), 端点 v i 所在的分区
标记为 P s , 端点 v j 所在的分区标记为 P t , 本文提出了一个分数度量 f (v i , v j ) 来确定这条边的分配, 如公式 (3) 所示.
( )
( )
t
s
s
f v i ,v j = argmax N − N ,N − N t (3)
v i v i v j v j
其中, N t 表示端点 v i 在分区 P t 中的邻居的数量, N s 表示端点 v i 在它所在分区中的邻居的数量, N s 表示端点 v j
v i v i v j
在分区 P s 中的邻居的数量, N t 表示端点 v j 在它所在分区中的邻居的数量. f (v i , v j ) 指出了将边 (v i , v j ) 分配到分区
v j
中, 并调整局部分区结构. 直觉上, 将边 (v i , v j ) 和端点 v i 分配到端点 v j 所在的分区 P t , 或者将边 (v i , v j ) 和端点 v j 分
配到端点所在的分区 P s , 这取决于哪种分配会使得边切割的数量更低.
● 顶点删除. 将一个顶点从现有的划分中删除, 那么同时会将该顶点的连接边一同删除. 顶点的删除有可能会
导致分区负载不平衡, 即会出现分区欠负载的情况. 因此, 当一个顶点删除时, 选择从高负载的分区中移动顶点到
欠负载的分区中, 并且要保证不能增加边切割的数量.
● 边删除. 对于删除一条边存在两种情况. 第 1 种情况是边的两个端点在不同分区中, 如果将该条边删除, 那
么会导致边切割的数量减 1. 对于这种情况, 不会做额外的动作. 第 2 种情况是边的两个端点在同一分区中, 由于
本文研究的是基于边割的图划分问题, 所以删除该条边不会导致划分质量的下降.
本节分别提出了不同图更新类型的动态处理策略. 但从问题分析中可知, 图的动态变化会影响划分质量, 在分
区边界区域会导致出现局部次优顶点划分. 因此在处理完每一个动态变化后, 在涉及动态变化的分区中, 通过基于
顶点组重分配的局部优化技术进一步提高图划分的质量, 使得达到局部最优顶点划分, 该局部优化方法接下来进
行介绍.
3.2.2 局部优化器
当图发生动态变化时, 对于涉及单元更新的分区, 在单元更新的附近有可能会出现局部次优顶点划分. 基于该
特点, 在 ED-IDGP 算法中, 本文提出一种基于改进标签传播算法的顶点组搜索策略搜索候选顶点组, 并且提出了
顶点组移动增益公式衡量最有益的顶点组 VG. 由于在基于改进标签传播算法的顶点组搜索策略的描述中需要用
到顶点组移动增益公式, 所以我们首先介绍本文提出的同时考虑边切割增益和负载平衡增益的顶点组移动增益公
式, 然后介绍基于改进标签传播算法的顶点组搜索策略.
定义 7. 负载平衡增益 (load balance gain). 对于一个给定的顶点组 VG, 将顶点组 VG 从分区 P s 移动到分区 P t
的负载平衡增益定义为公式 (4).
′
lb : gain s→t (VG) = LB(P)− LB(P ) (4)
其中, LB(P) 表示顶点组 VG 移动之前整个划分的负载平衡, LB(P ) 表示顶点组 VG 移动之后整个划分的负载平
′
衡. 由于负载平衡的变化只有顶点组 VG 所在的分区 P s 和目标分区 P t 决定, 所以顶点组 VG 的负载平衡增益也可
以用公式 (5) 表示.

lb : gain s→t (VG) = W (P s )− |V| |V| − W (P s −VG)− |V| |V| (5)

+ W (P t )−
+ W (P t +VG)−
k k k k
其中, W(P s ) 和 W(P t ) 分别表示 VG 移动之前分区 P s 和 P t 中的顶点数, W (P s )−W (VG) 和 W (P t )+W (VG) 分别表
示 VG 移动之后分区 P s 和 P t 中的顶点数.
定义 8. 边切割增益 (edge cut gain). 对于一个给定的顶点组 VG, 将顶点组 VG 从分区 P s 移动到分区 P t 的边切
割增益定义为公式 (6).