Page 410 - 《软件学报》2025年第5期
P. 410
2310 软件学报 2025 年第 36 卷第 5 期
1.2 基于 Poisson 分布的随机块模型
2011 年, Karrer 等人 [9] 假设两点间的连边服从 Poisson 分布并且融合节点度的幂律分布, 提出了度修正的随机
块模型 DCSBM. Chang 等人 [20] 假设网络的拓扑信息和属性信息都服从 Poisson 分布, 提出了融合网络拓扑信息和
节点属性的随机块模型 PSB_PG. 鉴于 PSB_PG 模型没有考虑节点度对社团检测精度的影响, 郑忆美等人 [21] 通过
引入节点度来刻画网络的无标度特性, 提出了度修正的属性网络随机块模型 DPSB_PG. Liu 等人 [22] 受 Newman 混
合模型 [23] 思想的启发, 在拓扑模型中引入了一组表征节点链接行为的参数, 并假设网络拓扑信息和属性信息都服
从 Poisson 分布, 提出了融合拓扑信息和节点属性信息的 GNAN 模型. Zhu 等人 [24] 在不考虑自环的情况下, 提出了
无自环随机块模型, 可以检测网络中的反社团 (anti-community) 结构. Wu 等人 [25] 通过对原始网络和模体网络
(motif network) 进行统一建模, 提出了混合阶随机块模型, 避免了现有社团检测方法中高阶和低阶连接模式的分离
和碎片化问题. Abossedgh 等人 [26] 在 DCSBM 的基础上增加每条边标签出现的概率, 提出了带标签的随机块模型,
改善了对个体行为的分析.
1.3 基于幂函数形式分布的随机块模型
2011 年, Shen 等人 [11] 假设两节点间的连边服从幂函数形式的分布, 提出了广义随机块模型 GSB. Yang 等人 [27]
认为两节点间的连边不仅与节点所在社团有关, 而且与节点的流行度有关, 通过引入节点流行度对网络中边的生
成进行建模, 提出了基于流行度的条件链接 (popularity-based conditional link, PCL) 模型, 并且利用内容判别模型
DC 对节点内容进行建模, 提出了 PCL_DC 模型. Chai 等人 [28] 不仅考虑了属性信息和节点度的幂律分布, 而且继
承了 PPL 模型 (popularity and productivity link model) [29] 和 GSB 模型的优点, 提出了 PPSB 模型 (popularity-
productivity stochastic block model). Jiang 等人 [12] 将 GSB 模型扩展到符号网络, 提出了符号广义随机块模型. Chen
等人 [30] 将节点属性以概率的形式融入 GSB 模型中, 提出了子空间的随机块模型, 在节点之间连边生成的过程中融
合拓扑信息和属性信息构建了隐网络, 避免了负采样策略. 虽然有研究人员对 GSB 模型进行了扩展, 但是没有考
虑节点度对网络链接的影响, 也没有对属性信息进行建模. 因此, 本文针对无向属性网络, 在 GSB 模型研究的基础
上, 对网络拓扑信息和属性信息同时建模, 并且引入节点的度刻画网络的无标度特性, 提出一种度修正的属性网络
广义随机块模型 DCGSB, 使其达到更好的社团检测精度.
2 DCGSB 模型
m 条
设 G(V,E,X) 是一个无向属性网络, 其中集合 V = {1,2,3,...,n} 由 n 个节点组成, 集合 E = {e 1 ,e 2 ,...,e m } 由
i
k
.
边组成, X = (x ik ) n×K 表示所有节点的属性矩阵. 若节点 具有属性 , 则 x ik = 1 ; 否则 x ik = 0 A = (a i j ) n×n 为网络的邻
c
接矩阵, 表示网络中节点之间的连边. 若节点对 (i, j) 之间存在连边, 则 a i j = 1 ; 否则 a i j = 0 . 假设网络 G 被分成 个
∪ c
不同的社团, 用 V 1 ,V 2 ,...,V c 表示, 则有 G = V r .
r=1
2.1 基于拓扑信息的生成模型
在标准的随机块模型 [7] 中, 概率矩阵 H = (h rs ) c×c 控制了网络中所有节点的连边概率, 当 i ∈ V r 且 j ∈ V s 时, 节点
j
i 与节点 之间的连边概率只与其所在社团有关, 即与 h rs 有关. 在 GSB 模型 [11] 中, Shen 等人通过引入节点隶属度
i
矩阵 B = (b ir ) n×c 放松了这个限制, 其中 b ir 表示节点 在社团 V r 中的概率. 但是 GSB 模型只适用于有向无属性网
络, 且将社团内的节点看作是无差别的, 忽略了节点度的异质性, 没有建模真实网络中节点度的幂律分布. 所以, 本
文针对无向属性网络, 在对网络拓扑信息建模的同时对节点属性进行建模, 并且引入节点的度刻画网络的无标度
特性, 更好地拟合了真实网络.
D = (d i ) 1×n 对网络中节点 与节点 之间存在连边的可能性有很
i
j
节点隶属度矩阵 B , 概率矩阵 H 以及节点度
大的影响. 一般地, 节点间存在连边的可能性随着节点度的增大而增大, 同时影响网络链接的生成. 假设节点 i 与
i
j
节点 j 之间边的生成服从幂函数形式的分布, 则社团 V r 中的节点 和社团 V s 中的节点 存在连边的可能性为:
rs
A = d i b ir h rs d j b js (1)
ij
