Page 413 - 《软件学报》2025年第5期

王笑 等: 面向属性网络社团检测的度修正广义随机块模型 2313

算法 1. DCGSB 的参数推断算法.

A, X, c, I T , ε ;
输入:
输出: B,H,Θ.
1. 计算节点的度 D = (d i ) 1×n ;
(0)
(0)
B ,H ,Θ (0) ;
2. 初始化
3. 根据公式 (8) 计算目标函数 L(B ,H ,Θ ) ;
(0)
(0)
(0)
t = 1 : I T do
4. for
5. E-step: 根据公式 (10) 计算 q ,γ ;
r
rs
i j ik
6. M-step: 根据公式 (11)、公式 (12) 计算 B ,H ,Θ (t) ;
(t)
(t)
7. 根据公式 (8) 计算目标函数 L(B ,H ,Θ ) ;
(t)
(t)
(t)

(t)
(t)
(t)

8. if L(B ,H ,Θ )− L(B (t−1) ,H (t−1) ,Θ (t−1) t = I T then
) < ε 或者
(t)
(t)
9. B = B ,H = H ,Θ = Θ (t) ; break;
10. end if
11. end for

3.2 初值设置
在算法 DCGSB 中, 概率矩阵 H 的初始化对其收敛速度有着较大的影响. 当 H 的初始化所产生的网络结构
与真实网络结构一致时, 算法就很容易收敛; 但当 H 初始化产生的网络结构与真实网络结构不一致时, 算法收
敛速度就会很慢. 为了让算法尽可能少的迭代次数就达到收敛, 在实验中, 利用最大熵 [32] 与最大似然的思想对
H 的初始值进行设置, 分为以下 3 种情况: (1) 当 H 对角线元素大于非对角线元素时, 对应网络的同配结构;
H 中的元素在某个值附近浮动时 (比如
(2) 当 H 对角线元素小于非对角线元素时, 对应网络的异配结构; (3) 当
0.5), 对应网络的其他结构. 针对每个网络, 我们首先将这 3 种情况分别执行若干次 (比如 10 次), 然后计算每种
情况下这若干次 (10 次) 似然函数的平均值, 最后将平均值最大的那种情况对应的 H 初始化形式作为 DCGSB
算法的初始化.

3.3 时间复杂度分析
DCGSB 模型的时间复杂度主要由 EM 算法的 E 步 (公式 (10)) 和 M 步 (公式 (11)、公式 (12)) 决定. 在每一
次迭代过程中, E 步的时间复杂度为 O(mc +nKc) ; M 步的时间复杂度为 O(nc+c +nKc) . 由于社团数 远远小于
2
2
c
c ≪ n , 因此 M I T , 故整个算法的
网络节点数 n , 即 步的时间复杂度可以写成 O(nKc) , 并且算法的最大迭代次数为
2
时间复杂度为 O(I T (mc +nKc)) .

4 基于 DCGSB 模型的社团检测
由于节点隶属度矩阵 B 刻画了网络中节点在社团上的分布情况, 我们的主要目标是求出节点隶属度矩阵
V r (r = 1,2,...,c) 的概率. 本文利用硬划分的方式来推断网络中节点的
B = (b ir ) n×c , 即每个节点属于任意一个社团
社团隶属度, 即利用 b ir 的最大值限定一个节点只能属于一个社团. 由于 EM 算法求解模型参数时引入了隐变量,
不能直接对 b ir 进行处理. 为了得到硬划分, 本文对参数 b ir 与 h rs 设置了一种运算, 即:

c ∑
b ir h rs
s=1
M ir = (13)
c ∑
b ir h rs
r,s=1
∗
DCGSB r = argmax M ir 得到节点 r .
∗
算法可通过优化 i 最终属于社团
r