Page 409 - 《软件学报》2025年第5期
P. 409

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


                    近年来, 在许多学科中, 将结构化数据建模成复杂网络的趋势日益增长. 复杂网络作为一种描述实体之间关系
                 的抽象概念, 已成为数据科学研究的热点. 网络分析也日益受到数学、计算机科学以及生物学等领域的关注                                   [1,2] .
                 社团检测是网络分析的一项重要任务, 其目的是将网络划分为多个社团, 使得同一社团内的节点链接比较紧密, 不
                 同社团间的节点链接比较稀疏          [3] .
                    社团检测可看作网络节点的聚类问题. 经典的启发式聚类算法主要包括基于层次聚类的凝聚式算法                                  (FN) 和
                                                                                                     [4]
                              [5]
                 分裂式算法    (GN) 等. 网络结构和离散优化的学习方式对启发式算法的影响较大, 导致其很难描述比较复杂的网
                 络数据  [6] . 生成模型在启发式算法的基础上利用概率分布对网络进行建模, 把社团检测问题转化成统计推断问题.
                                                    [7]
                    随机块模型     (stochastic block model, SBM) 是基于随机等价思想建立的一类概率生成模型, 它不仅可以生成
                 各种网络, 反过来, 还可以探测网络的社团结构. SBM              利用概率分布对网络进行建模, 把社团检测问题转化为带
                 有约束条件的参数估计问题, 具有很强的理论支撑性. 同时, SBM                  不需要提前假设网络中都存在哪种网络结构,
                 在不知道网络结构的情况下可以准确地识别真实结构, 能识别的结构包括社团结构、多分结构以及混合结构
                 等. 具有代表性的     SBM  有: 2008  年, Airoldi 等人  [8] 提出的混合隶属度随机块模型; 2011  年, Karrer 等人  [9] 提出的
                 度修正随机块模型; 2019      年, Lu  等人  [10] 提出的正则化随机块模型等. 这些模型在社团检测的过程中可以借助优
                 化算法对其参数进行估计, 如         MCMC (Markov chain Monte Carlo) 算法、置信度算法、期望最大化算法与变分推
                 断算法等.
                    广义随机块模型      (general stochastic block model, GSB) [11] 是基于链接社团的思想提出来的, 它不仅可以检测传
                 统的社团结构, 还可以检测多分结构、混合结构等多种网络结构. 在该模型中, 假设边的产生仅与两个端点所在社
                 团有关, 将节点看作是无差别的, 也没有考虑属性信息对社团检测精度的影响. 后来, Jiang                      等人  [12] 虽然将其扩展到
                 了符号网络, 但依然没有考虑属性信息对社团检测精度的影响. 因此, 本文在                      GSB  模型的基础上, 针对无向属性网
                 络, 综合考虑了网络拓扑信息和属性信息对社团检测精度的影响, 在对网络拓扑信息建模的同时对节点属性进行
                 建模, 并且引入节点的度刻画真实网络的无标度特性, 提出了一种度修正的属性网络广义随机块模型                                DCGSB. 值
                 得注意的是, DCGSB    模型是对    GSB  模型的一种扩展, 两者的区别在于          DCGSB  模型不仅对节点属性进行建模, 而
                 且引入了节点的度这个观测变量, 可以更好地发现网络中的社团结构.
                    本文第   1  节介绍和分析    SBM  的相关工作. 第   2  节给出  DCGSB  模型的建模过程. 第     3  节介绍  DCGSB  模型的
                 参数估计及时间复杂度分析. 第          4  节介绍基于   DCGSB  模型的社团检测过程. 第      5  节给出实验结果与分析. 总结在
                 第     6  节中给出.

                 1   相关工作

                    随机块模型是一种经典的网络分析模型, 可以描述不同类型的网络结构并还原网络的生成. SBM                              按照概率分
                 布可分为   3  类: 基于  Bernoulli 分布的随机块模型、基于     Poisson  分布的随机块模型以及基于幂函数形式分布的随
                 机块模型.

                 1.1   基于  Bernoulli 分布的随机块模型
                    2008  年, Airoldi 等人  [8] 假设两点间的连边服从  Bernoulli 分布, 提出了混合隶属度随机块模型. Xing       等人  [13] 将
                 混合隶属度随机块模型扩展到动态网络, 提出了动态混合隶属度随机块模型. Aicher 等人                        [14] 假设边的权重服从指
                 数族分布, 并将其引入      SBM  中, 提出了加权随机块模型, 将        SBM  扩展到了加权网络. Li 等人     [15] 对网络结构的异质
                 性进行建模, 提出了度修正的重参数化随机块模型, 可以表征具有异构块和度分布的各种网络结构. Qiao                              等人  [16]
                 通过引入度衰减变量对所有节点上的不同度分布进行编码, 提出了幂律度随机块模型, 在真实网络中近似地保持
                 了无标度特征. Wu     等人  [17] 结合节点流行度刻画网络的无标度特性, 提出了动态网络社团检测随机块模型, 解决了
                 动态网络中的社团检测和演化追踪问题. Xu              等人  [18] 通过对网络中噪声节点建模, 提出了鲁棒随机块模型, 缓解
                 了网络中的噪声问题. Liu       等人  [19] 通过神经网络将节点属性引入到         SBM  中, 提出了属性网络生成模型          ANGM
                 (attributed network generative model), 可以检测同配网络和异配网络.
   404   405   406   407   408   409   410   411   412   413   414