论文部分内容阅读
由于复杂网络（数学上常称为图）规模宏大、结构复杂、难以理解等原因,人们十分重视能分析网络整体统计特性的方法,如聚类分析,在网络分析中,常称为社区探测.尽管聚类分析是个古老的话题,但图聚类和度量空间中的数据点聚类有很大的不同,本质区别是前者与边的连接模式相关,后者则与度量空间中的“距离”有关.由于网络是一种关系结构,导致了网络连边之间的相依性.网络复杂的相依性不符合标准统计学中的常见假设,给聚类分析带来了新的挑战.随机块模型是一类基于随机等价性思想提出的概率生成模型,可以灵活地引入参数,反映节点不同类型的连接模式,从而生成各种不同的网络结构,给研究网络的整体统计特性如聚类分析带来了便捷.然而,随机块模型中存在一些关键问题亟待解决,主要表现在三个方面:（1）如何确定社区的数目,即模型选择问题;（2）如何拓展模型,将网络的附属信息融合进模型中以提高聚类的质量;（3）如何设计高效的算法以适应不断增长的网络规模.本文将基于节点的连接模式视角,依托随机块模型对以上三个问题展开研究.具体有:（1）诸多的随机块模型都存在模型选择的问题.事实上,模型选择问题是网络聚类分析中的一个待定问题,没有广泛认同的模型选择准则.现有多数方法都仿照经典统计学中的模型选择准则,在模型精度和模型复杂度之间寻求最佳平衡.与之不同的是,本文基于信息熵（entropy）和混合系数提出一种方法,侧重于提取混合系数中含有的信息.我们首先注意到混合模型中的混合系数（混合先验分布）含有社区规模的信息,利用熵提取混合系数中含有的信息,去除含有信息太少（即社区规模太小）的社区就可以确定社区的数目.在第3章中,结合信息熵和NMM实现了上述的想法.NMM（Newman’s mixture model）是基于随机等价性思想提出的概率生成模型,能探索各种网络结构,包括社区结构、二分结构、核心-边缘结构和混合结构等（本文称为广义社区结构）,但该模型需要事先指定社区的数目.针对此,提出了一种熵正则化混合模型（称为EMM）.设计了具有一定自适应性的熵系数,使得该系数同时具有惩罚功能和平衡功能.该模型能够自动地推断网络中包含的社区个数,同时能够识别网络的各种结构.使用EM（expectation-maximization）算法得到模型的各个参数估计,特别是极小化混合系数的熵,可以逐步丢弃包含节点很少（即信息很少）的社区,从而在算法收敛时能自动地得到社区的数目.在人工网络和真实网络上的实证研究表明,所提出的模型EMM具有较好的效果.尽管EMM是结合熵和NMM提出的,这里基于熵提取混合系数信息的想法也适用于其它含有混合分布的模型.基于熵和混合系数的方法扩展了模型选择的方法.（2）融合网络的附属信息（如节点的属性信息）是对随机块模型的一个重要扩展,可以提高社区探测的质量.然而,网络的属性信息类型多样,如何把属性信息融合进模型是个有挑战性的问题,融合不当反倒可能成为干扰信息.多数已有的模型只能探测社区内部连接紧密但社区之间连接稀疏的社区结构.在第4章中,通过节点和属性共享节点的潜在位置,构建了一个概率生成模型PSBPG,融合了网络的拓扑信息和节点的属性信息,不仅比单独利用拓扑信息能更准确地探测社区,而且能提供社区的语义解释.其中生成拓扑信息的模型是基于随机块模型中块结构的假设提出的,能探测多种网络结构.生成节点属性信息的概率生成模型是基于属性高维稀疏的假设提出的.生成连边和属性的模型均服从Poisson分布.统一的分布形式使得似然函数便于用EM算法学习模型参数.在含有各种结构的人工网络和实际网络上,和已有的几种方法相比,显示了提出方法的竞争力.（3）像第3章和第4章中采用的EM算法主要存在两个问题:一是算法复杂度高,特别生成拓扑信息的模型采用经典的SBM（stochastic blockmodels）中块结构的假设时;另一个是EM算法推断的模型参数依赖于给定的数据集,容易产生过拟合现象.针对上述的两个问题,在第5章中,基于块结构的假设,提出了一个联合概率生成模型.引入变分分布族来近似模型中社区隶属度后验条件分布.通过变分贝叶斯EM算法得到了模型参数的非渐近估计.根据这些估计,设计了快速计算节点潜在位置后验分布算法VI-GCD.该算法能发现属性图中的广义社区,得到和社区相关的属性,同时改进了EM算法中复杂度高和过拟合的问题,可以在大规模网络上实施.