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

2312 软件学报 2025 年第 36 卷第 5 期

b js
a ij b ir
i j
θ rk x ik a ij h rs
b ir b js
h rs d i
d j
V r V s
(a) GSB 模型 (b) DCGSB 模型
图 1 GSB 与 DCGSB 建模过程示意图

3 DCGSB 模型的参数估计及时间复杂度分析

3.1 DCGSB 模型参数的 EM 算法估计
DCGSB 模型总共包含 3 种变量, 分别为: 观测变量 A 、 X 和 D ; 隐变量 Q = (q ) n×n 和 Υ = (γ ) n×K ; 模型参数
r
rs
ik
ij
Θ = (θ rk ) c×K . 由于模型中存在隐变量, 无法直接对似然函数进行求解, 期望最大化
B = (b ir ) n×c 、 H = (h rs ) c×c 和
(expectation-maximum, EM) 算法 [31] 是常见的隐变量估计方法, 能很好地处理此类问题. 所以, 本文采用 EM 算法对
模型进行参数估计. 推断过程如下.
对联合概率模型公式 (7) 取对数得到对数似然为:

   
c n K c
∑  ∑ ∑ ∑ 
n ∑
     
L(B,H,Θ) =  d i b ir h rs d j b js + x ik ln     (8)


a ij ln
   d i b ir θ rk 
 
i,j=1 r,s=1 i=1 k=1 r=1
在期望 B,H,Θ 固定后, 利用 Jensen 不等式得到对数似然的下界为:
E (expectation) 步, 参数
c [ ( )] K c [ ( )]
n ∑ ∑ n ∑ ∑ ∑
r
rs
¯ L(B,H,Θ) = a ij q ln d i b ir h rs d j b js + x ik γ ln d i b ir θ rk (9)
ij q rs ik γ r
i,j=1 r,s=1 i j i=1 k=1 r=1 ik
其中,

d i b ir h rs d j d js d i b ir θ rk
r
rs
q = , γ = (10)
ij ik
c ∑ c ∑
d i b ir h rs d j d js d i b ir θ rk
r,s=1 r=1
i
其中, q rs 表示节点 i, j 分别在社团 V r 和 V s 中且节点对 (i, j) 之间存在连边的概率; γ r ik 表示节点 在社团 V r 中且具
i j
有属性 k 的概率.
在最大化 M (maximum) 步, 隐变量 q ,γ r ik 固定, 根据 Lagrange 乘子法可以得到 b ir ,h rs ,θ rk 这 3 个参数的估计,
rs
ij
分别为:

c
n ∑ ∑ K ∑
rs
a ij q + x ik γ r ik
ij
j=1 s=1 k=1
b ir =   (11)
n c K
∑ ∑ n ∑ ∑ 
 
  rs r  
d i ×   a i j q + x ik γ 
ij
 ik 
i,j=1 s=1 i=1 k=1

n ∑
n ∑
a ij q rs x ik γ r
i j ik
i,j=1 i=1
h rs = , θ rk = (12)
c
n ∑ ∑ K
n ∑ ∑
a i j q rs x ik γ r
ij ik
i,j=1 r,s=1 i=1 k=1
参数估计方法的具体步骤如算法 1 所示.