基于生成模型的大规模网络广义社区发现方法研究

发布时间：2020-11-09 20:41

　　 随着互联网技术和数字化技术的发展,各类在线社会网络,如Twitter、 LinkedIn、Facebook、新浪微博、人人网,逐渐成为人们生活、学习、工作不可缺少的平台。这些在线社会网络每天产生庞大、繁杂的链接数据和内容数据。链接数据隐含社会网络潜在结构和交互规律,内容数据包含丰富的文本、图像和其它多媒体数据,为数据挖掘提供了丰富的信息。对这些网络数据进行潜在结构挖掘和分析为各个领域提供了史无前例的机会和挑战。 传统社区发现是当前最主要的网络潜在结构挖掘和分析方法,其假设网络中只有类内节点链接紧密、类间节点链接稀疏的结构。但网络中是否存在社区结构或其它类型结构,人们事先未知。因此,传统社区发现方法在网络中没有社区结构或存在其它类型结构时可能会失效。用于网络潜在结构发现的随机块模型对多种类型网络结构(如社区结构、二分结构、星型结构等)建模,可实现多种类型网络潜在类结构的发现。该类结构假设：与其它节点链接概率相同的节点属于同一类,这使得类结构不仅包括同类链接紧密、异类链接稀疏的传统社区结构,还包括同类链接稀疏、异类链接紧密的二分图结构及其它复杂结构。将这类结构称为“广义社区结构”。现有广义社区发现生成模型以及参数求解算法,还不能有效挖掘庞大的复杂网络内的潜在结构。因此,有必要研究基于生成模型的广义社区发现方法。本论文研究如何将网络特性融入广义社区发现概率生成模型之中,以及如何设计高效、准确的参数求解算法。主要完成了以下几个方面的研究内容： 1)提出了一种基于扩展随机块模型GSB(General Stochastic Block model)的快速广义社区发现算法FGSB(Fast GSB)。GSB模型基于链接社区思想发现广义社区,但其参数估计算法的时间复杂度限制了其在中大型规模网络上的应用。为了提高GSB模型参数估计算法的运行效率,我们设计一种广义社区发现的快速算法FGSB。该算法在迭代过程中使用如下两种策略动态学习模型参数：①重新组织参数降低算法存储空间；②裁剪已收敛节点和边相关的参数以节省算法运行时间。实验表明：FGSB与GSB有相同的结构发现能力,但FGSB耗费的存储空间和运行时间比GSB低。 2)提出了一种广义社区发现链接模型PPSB(Productivity-Popularity Stochastic Block model),并将其与内容模型DC(Discriminative Content)相融合,进而提出内容网络上的广义社区发现模型PPSB-DC.已有随机块模型不能对节点度的幂率分布、节点重叠性和网络广义社区统一建模,不能拟合实际幂率度分布网络的真实特性。因此,PPSB模型在有向网络生成过程建模中考虑四个因素：节点生成度、节点流行度、节点混合隶属度和社区间链接概率,该模型具有随机块模型发现广义社区的能力,还可以对节点幂率度分布进行拟合,从而提高了广义社区发现的准确率。为了利用实际网络中节点上富含的内容信息,我们提出了一种融合网络拓扑结构和内容属性的PPSB-DC模型,该模型进一步提高了广义社区发现的准确率。相关实验验证了PPSB模型和PPSB-DC模型的有效性。 3)提出了一种广义社区发现的三层贝叶斯网络模型GPPSB (Generalized PPSB),并基于该模型设计了大规模网络广义社区发现随机变分推理算法GPPSB-SVI。虽然PPSB链接模型可同时对多类型网络结构和节点度幂率分布建模,但该模型没有对网络节点隶属度和类间链接概率生成过程建模,致使模型易随着训练集合数据集的增长而过拟合,也不易为训练集合之外的网络实体进行链接预测。另外,PPSB模型的参数估计算法复杂度较高,不适于处理大规模网络。因此,我们设计了一种三层贝叶斯网络模型GPPSB,该模型在PPSB的基础上引入节点隶属度和类间链接概率矩阵的先验分布。并给出了一种基于随机变分推理(Stochastic Variational Inference)的快速估计算法GPPSB-SVI。与同类算法的比较实验结果显示：GPPSB-SVI可更快、更准地实现广义社区发现。 4)提出一种基于混合模型的广义社区发现在线EM(Expectation Maximiza-tion)算法Online-VEM(online Variational EM).一方面,已有的基于随机块模型的在线EM算法OEM可快速实现大规模网络的广义社区发现,但网络中社区个数较多时该算法的时间复杂度较高(O(mK2),其中m表示边数,K表示社区数)。另一方面,目前存在与社区个数成线性复杂度(O(mK)的广义社区混合模型NMM及其变型ENMM,但是其参数估计算法每次迭代需要在所有网络链接上操作,致使该算法不能处理百万级或更大规模的网络。为此我们提出了一种基于ENMM模型的在线广义社区发现算法—在线变分EM算法Online-VEM.该算法首先估计新增加节点的类隶属度后验分布,然后根据上次迭代估计的模型参数和新增节点类隶属度后验分布更新当前模型参数。无论与已有的在线算法OEM相比,还是与复杂度较低的混合模型NMM和ENMM的参数估计算法相比,Online-VEM算法耗时更少且不降低算法准确率。
【学位单位】：北京交通大学
【学位级别】：博士
【学位年份】：2015
【中图分类】：TP311.13;O157.5
【部分图文】：

种类型结构的混合。大多传统社区发现方法假设网络中存在链接紧密的子图结构，且只能发现此类结构。当网络中存在多种类型结构（如图1.1)【iG]或网络中不存在传统社区（如图1.2)【11]时，该类方法不能有效地识别网络的真实结构。如图1.1中，同时存在多分结构、社区结构；图1.2为生物链网络，具有层次结构。3)传统社区发现不能在发现网络社区结构的同时，识别出类间的交互规律：传统社区发现方法的目的是将网络节点按照链接紧密性聚类，不能提供社区间链3

图1.2 二分图网络示例Fig. 1.2 An example of bipartite graph接模式，不易于网络结构可视化及直观了解网络交互规律。对网络结构无任何先验的情况下，基于统计推理的网络潜在结构发现方法不仅可识别社区结构，还可识别更多其它类型的网络结构[2，3]。受概率图模型[12，13]理论发展影响，该类方法成为近来最流行的网络结构发现方法该类方法根据实际网络特性对网络生成过程建模，利用概率图模型的贝叶斯网络或马尔科夫网络表示模型

9110010000图2.1结构对等性示例网络及邻接矩阵Fig. 2.1 An example of network with structural equivalence and its adjacency matrix.炎-1 炎:2 炎:3类 1 0.7 0.3 0.4 1炎:2 0.3 0.7 0.4炎:3 0.4 0.3 0 V图2.2图2.1网络基于节点结构对等性划分后的块矩阵及简化块网络Fig. 2.2 Block matrix and simplified network of the network in Fig.2.1 partitioned by structuralequivalence.Modeling),相应的模型为块模型(Block Model)。块模型用来发现网络角色间的链接特征而不是节点间的链接特征，该模型根据节点相似性将节点聚类，相似性有结构对等性(Structural Equivalence)和正则对等性(Regular Equivalence)。在Lorrain和White的研究论文[77】中出现结构对等性，定义为：两个节点和相似的节点链接，则这两个节点具有结构对等性。结构对等性思想详细解释如下：假设网络中；V个节点分为A：个块，将结构对等的节点合并为一个超节点或块。令是图G(;V，}0的邻接矩阵，如果两个节点和6与其它节点的链接模式和Cfc相似则它们结构对等，属于相同的块/1。链接模式形式化为：Ca = {Y(a,i ehk) ： h) K Cb. (2-1)其中/是《
【参考文献】

相关期刊论文 前3条

1 杨博;刘杰;刘大有;;基于随机网络集成模型的广义网络社区挖掘算法[J];自动化学报;2012年05期

2 张宏毅;王立威;陈瑜希;;概率图模型研究进展综述[J];软件学报;2013年11期

3 柴变芳;于剑;贾彩燕;王静红;;一种基于随机块模型的快速广义社区发现算法[J];软件学报;2013年11期

本文编号：2876943