论文部分内容阅读
复杂网络是现实世界复杂系统的抽象表现形式,具有广泛的研究价值和应用前景。例如,挖掘复杂网络隐含结构模式对于发现复杂系统中隐含的功能模块、理解各模块之间潜在的联系以及预测复杂系统的动态演化等具有重要的意义。随机块模型(Stochastic block model,SBM)在复杂网络研究方面优点众多,具有可解释性、表达能力、泛化能力及灵活性等,已被用于各种网络分析任务,如社区发现、链接预测、网络表示学习等。然而,现实世界网络具有链接稀疏、规模庞大、结构复杂等特点,使得SBM在复杂网络研究中仍存在以下问题。(1)符号网络是常见的复杂网络类型之一。大多数符号网络的SBM学习算法是非监督的,当网络中存在噪声或网络较为稀疏时,这些方法在隐含结构发现任务上表现不佳。因此,能否提出一个基于半监督学习的SBM模型,使其能够提升挖掘噪声和稀疏符号网络中社区和多分结构的精度?(2)在实际应用中,需尽可能高效地找到最优的SBM模型,从而拟合现实世界复杂网络。然而,对于给定的网络,当网络中隐含结构数目未知时,学习最优的SBM仍是一个NP难问题。因此,能否提出一个SBM的快速学习方法,使其既具有模型选择能力,又在网络分析任务中保持较好的性能?(3)属性网络表示学习是网络科学研究热点之一。然而,现有属性网络表示学习方法主要考虑网络局部信息而忽略了全局信息,在异配网络上表现不佳。因此,能否将SBM应用于属性网络表示学习任务,利用其表达能力,同时处理同配网络和异配网络?基于以上问题,本文的研究工作主要围绕SBM的模型扩展、快速学习以及模型应用三个方面展开,具体的贡献如下:(1)提出新颖的半监督符号SBM模型及基于变分贝叶斯推理的学习算法,挖掘噪声和稀疏符号网络中隐含结构。具体地,引入描述节点所属块与节点标签关系的参数,并利用部分标签提高模型发现网络隐含块结构的性能。本模型采用两个向量分别表示块内和块间节点之间具有不同类型链接的概率,从而刻画网络中隐含的结构类型。基于变分贝叶斯理论,本文提出了高效的半监督学习算法,从而估计模型参数和隐变量。实验结果表明,本文模型优于其他对比算法,且该优势在噪声和稀疏网络上更明显。(2)提出基于泊松分布的重定义SBM及基于期望最大化(EM)的blockwise算法,有效处理大规模网络。与经典SBM模型相比,本模型假设网络链接生成过程服从泊松分布,使算法时间复杂度与网络边数相关,而非节点数平方。其次,该模型重定义边的生成方式:边的生成取决于块与节点间链接概率,而非块与块之间链接概率。该方法解决了隐变量后验元素之间的依赖问题,使得该模型可用EM算法高效地更新隐变量后验分布。在学习过程中,每次迭代时,评价每个块的“质量”并删除不符合条件的块,并行地估计参数和选择模型。实验结果表明,本文模型及其算法在精确性和可扩展性方面同时优于现有算法。(3)提出面向属性网络表示学习的生成模型,利用随机块模型的表达能力,解决同配网络和异配网络表示学习问题。具体地,网络节点分配到各个块中,其中相同块内节点具有类似的链接模式,这些模式可定义具有社区的同配网络或具有其他结构的异配网络。为保留属性信息,假设每个节点具有一个与块相关的隐含表示,同时节点的表示和属性之间具有可用神经网络刻画的非线性关系。实验结果表明,在网络分类和聚类任务中,本文提出的算法优于属性网络表示学习对比算法,且在异配网络上优势更明显。