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

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

考虑所有社团, 节点对 (i, j) 生成连边的可能性为:

c ∑
ˆ A i j = (2)
d i b ir h rs d j b js
r,s=1
给定模型参数 B,H 和观测变量节点的度 D = (d i ) 1×n 后, 生成网络 G 的概率 P(A|B,H,D) 为:

n ∏
P(A|B,H,D) = ( ˆ A ij ) a ij (3)
i,j=1
∑ c ∑ n ∑ n
˜
其中, 概率矩阵 H 是对称的且满足约束条件 h rs = 1 , 节点隶属度矩阵 B 满足约束条件 d i b ir = b ir = 1 .
r,s=1 i=1 i=1
H 对角线元素
由于概率矩阵 H = (h rs ) c×c 的引入, 继承了随机块模型的优点, 可以检测多种网络结构, 比如概率矩阵
大于非对角线元素时, 可以检测传统的社团结构; 对角线元素小于非对角线元素时, 可以检测网络的异配结构; 其
他情况可以检测更多的网络结构.

2.2 基于属性信息的生成模型
在属性网络中, 节点属性通常用高维向量表示. 如果一组高维向量中具有相同分量的个数越多, 其对应节点构
成的网络拓扑结构一致的可能性越大, 越容易形成社团结构. 假设网络中节点属性的生成也服从幂函数形式的分
k
布, θ rk 为社团 V r 具有属性 的概率, Θ = (θ rk ) c×K 是社团相关属性矩阵. 一般地, 对于不同类型的网络, 节点度与节
V r 中节点 具有属
i
点属性的关系可能呈现多样性. 但在一些网络中, 节点度与节点属性具有相关性. 基于此, 社团
i
性 k 与节点隶属度 b ir 、节点的度 d i 以及社团相关属性 θ rk 有关, 社团 V r 中节点 具有属性 k 的可能性为:

r
ˆ X = d i b ir θ rk (4)
ik
考虑所有社团, 节点 i 具有属性 k 的可能性为:

c ∑
ˆ X ik = (5)
d i b ir θ rk
r=1
∑ n ∑ n ∑ K
其中, d i b ir = ˜ b ir = 1, θ rk = 1 满足归一化约束条件.
i=1 i=1 k=1
给定模型参数 B,Θ 以及观测变量节点的度 D 后, 网络中生成节点属性的概率 P(X|B,Θ,D) 为:

K
n ∏ ∏
P(X|B,Θ,D) = ( ˆ X ik ) x ik (6)
i=1 k=1

2.3 融合拓扑信息和属性信息的度修正广义随机块模型
假设网络拓扑信息和节点属性的生成过程相互独立, 则度修正的属性网络广义随机块模型 DCGSB 的联合概
率为:

P(A,X|B,H,Θ,D) = P(A|B,H,D)× P(X|B,Θ,D)
  a i j   x ik
n K c
n ∏∑  n ∏ ∏ ∑
    

=    d i b ir h rs d j b js ×   d i b ir θ rk   (7)


   
 
i,j=1 r,s=1 i=1 k=1 r=1
如图 1 所示, 与 GSB 模型相比, DCGSB 模型进一步假设一条边的生成概率还依赖于其两端节点的度, 并且针
对无向属性网络, 在对网络拓扑信息建模的同时对节点属性进行建模, 其节点属性的生成也服从幂函数形式的分
布. 图 1 中阴影圆表示观测变量, 图 1(a) 中的无阴影圆表示隐变量, 虚线表示两个变量之间的关系, 实线表示观测
到的连边; 图 1(b) 中的无阴影圆表示模型参数. DCGSB 算法的建模过程如图 1(b) 所示. 根据建模过程, 网络中节
点间连边的生成和节点属性的生成步骤可以总结如下.
j
(1) 从社团 V r 和 V s 中分别以概率 b ir 和 b js 抽取节点 i 和 .
∑
c
j
(2) 在节点 i 和 之间以概率 ˆ A ij 生成连边, 其中 ˆ A i j = d i b ir h rs d j b js .
r,s=1
(3) 从社团 V r 中以概率 θ rk 选择一种属性 k .
∑ c
(4) 给节点 i 以概率 ˆ X ik 选择一种属性, 其中 ˆ X ik = d i b ir θ rk .
r=1