Page 225 - 《软件学报》2026年第2期
P. 225
704 软件学报 2026 年第 37 卷第 2 期
) p
P ∑ (
T = θ p AD −1 (1)
p=0
−tt p / [28]
t
其中, T 是列随机的广义聚合矩阵, P 是要聚合的邻居的跳数. θ p = e p ! 是权重系数, 其中 是运行时间 , 并严
P ∑
格满足条件: θ p = 1, θ p ∈ [0,1]. 邻接矩阵 A 是从粗图 G l 导出的, 而度矩阵 D 是节点度的对角矩阵, 其元素 D ii 表
p=0
N ∑
示节点 i 的度, 即 D ii = A i j .
j=1
公式 (1) 旨在反映 P 跳邻域节点的影响, 并对特征和边的噪声进行平滑处理. 这一特性在后续的细化阶段和
重构过程中显得尤为重要 [29] . 基于局部语义和结构信息, 节点 (u,v) 之间的相似性 s u,v 可以计算如下.
T ( )
u
s u,v = X A u,v ,λT u,v X v (2)
其中, λ 作为平滑参数, 用于调整局部结构特征的影响. 经过 L 次粗化迭代, 本文得到了最小的粗化图 G L . 具体粗化
和采样过程如算法 1、2 所示.
算法 1. 图粗化阶段伪代码.
输入: 原始图 G 0 = G; 最大迭代次数 L; 粗化后图的预期节点数 N stop ;
G 1 ,G 2 ,...,G L .
输出: 一系列规模逐渐减小的图
1. 初始化迭代层次 l = 0
2. 当 l < L 且 |V l | > N stop 时:
|V l+1 | ⩽ |V l |)
3. (不变量: 对所有 l ⩾ 0, 有
4. 初始化空集 M l 作为 G l 的匹配集
5. 遍历图 G l 中的所有节点:
6. 如果节点 u ∈ V l 未被匹配或访问:
7. 如果节点 u 存在 1-跳邻居:
8. 使用公式 (2) 找到与节点 u 最相似的节点 v ∈ V l
9. 将 (u,v) 添加到匹配集 M l 中
v 为已匹配
10. 标记节点 u 和
11. 否则
12. 标记节点 u 为已匹配
G l+1 : G l+1 ← ContractGraph(G l , M l )
13. 收缩图 G l 以创建
14. l ← l+1
15. 函数 ContractGraph(G l , M l ):
16. 初始化空图 G l+1
17. 对于匹配集 M l 中的每一对 (u,v):
18. 在 G l+1 中创建一个新节点 w, 代表合并后的节点 u 和 v
19. 对于节点 u 或 v 在 G l 中的每一个邻居 x:
20. 在 G l+1 中添加边 (w, x)
21. 更新 G l+1 中边 (w, x) 的权重为 G l 中边 (u, x) 和 (v, x) 权重之和
22. 对于图 G l 中的每一个未匹配节点 u:
G l+1 中
23. 将节点 u 及其边复制到
24. 返回图 G l+1
