3.6　大规模复杂网络的多元结构知识发现

网络在现实世界中广泛存在，复杂系统中的相互作用和大数据的关联关系都可以抽象地表示为网络。泛在性使围绕网络的基础研究具有非常深远的科学意义，相关理论和方法的突破会同时推动多个学科领域的发展，产生巨大的价值和影响。无标度网络的提出者、著名物理学家Albert L. Barabási教授指出：“21世纪将是网络理论的世纪，当前正在形成的理论和算法框架将成为众多研究和应用领域新的驱动力。”李国杰院士指出：“大数据面临的科学问题本质上可能就是网络科学问题，复杂网络分析应该是数据科学的重要基石。”网络研究已成为当前最前沿的多学科交叉研究领域之一。

从1998年开始，人们陆续发现了普遍存在于不同网络中的多种结构，包括社区、领结、权威、中枢、二分、多分、边缘和层次等，并对它们的功能、性质和发现方法进行了深入研究。其中，社区发现还成为数据挖掘和机器学习领域的研究热点，各种算法层出不穷。然而在2010年之前，人们对网络结构的认识仅局限于单一结构，这期间发表的大量论文也都围绕着某一种具体的结构展开，而对于“网络中是否会同时存在多种结构”这一更为深刻的问题还鲜有探索，更不清楚该如何发现共存网络中的多种结构及其关联关系。对于一个复杂网络系统，如果能从中发现由多种基本结构组成其宏观结构的方式，基于这些结构和结构间的关系，以及人们对各种结构性质与功能的已有认识，就有望知道该网络所表现出的整体功能是如何由多个基本结构协作产生的。因此，相对于单一结构研究，“将多种结构统一起来”的研究思路更有助于揭示复杂系统的组成方式、运行机制、结构与功能的内在联系。在此背景下，吉林大学课题组从2010年开始倡导对“多元结构”概念和发现方法的研究，推动网络结构分析从“单一”向“多元”方向发展，并取得了一些重要进展。

理论上，多元结构分析面临的主要难题是如何从零先验知识的网络中正确发现共存其中的多种结构及其相互间的复杂关系。单一结构发现方法（如社区发现）只能发现事先指定好的结构，对此问题难以胜任。研究发现，网络中具有统计意义的结构都可由一定数量的“同构”结点共同“凸显”而成。基于此，研究人员提出了用于定义多元结构的多尺度随机块模型，能够以一致的方式定义现存的各种单一结构及由它们组成的多元结构。基于该模型，多元结构发现问题转换成了统计网络学习问题：基于被观察的网络学习出最优的多尺度随机块模型，进而采用同构子图识别算法从中抽取基本结构及相互关系。相对单一结构发现方法，提出的多元结构发现方法能够自主决策从零先验知识网络中“发现什么”及“如何发现”。基于该方法的实证研究发现：社会、生物和经济等多个领域的复杂系统都同时包含多种基本结构，它们以重叠、组合或嵌套的方式共存于网络的不同尺度上，共同形成一个异构层次形式的“多元结构”。

吉林大学课题组的工作较为系统地解决了复杂网络多元结构分析和应用的一些关键问题，可概述为以下3个主要方面。

1）随机块模型（Stochastic Block Model，SBM）是一类重要的统计网络模型，是建模和发现多元结构的理论基础。吉林大学课题组首次提出了SBM的并行学习机制，使其最坏时间复杂度从现有的O(n5)降低至O(n3)，在保持学习精度和模型灵活性的前提下大大降低了SBM学习时间复杂度。同时，吉林大学课题组还提出了第一个符号网络统计学习模型，将多元结构分析的应用领域从一般网络拓展到包含更多语义信息的符号网络。

2）将网络多元结构分析方法应用于社会化推荐，吉林大学课题组提出基于信任的社会化协同过滤推荐算法和协同矩阵填充概率模型，更好地解决了数据稀疏和冷启动问题。该工作启发了后续研究，后续多个工作都将其作为社会化协同过滤的基准算法进行对比。

3）吉林大学课题组将网络多元结构分析方法应用于计算流行病学领域，首次研究了社会经济因素对输入型疟疾传播的影响，提出了异构传播网络概念和基于开源异构数据挖掘的跨国界疟疾主动监控方法，研制出疟疾智能监控系统，为开源信息融合与挖掘的研究提供了范例和新思路；该课题组提出并解决了“隐含数据的稀疏编码”问题，进而发明了面向大规模人口的动态接触追踪技术，对构建传染病的主动防控策略具有重要意义；同时，该课题组面向动态接触的传染病早期监控策略优化方法，提出了一种基于组稀疏贝叶斯学习的主动监控规划方法。

上述工作初步建立了多元结构分析的理论框架，推动了该领域的研究及其在社会化信息检索和计算流行病学领域中的应用，引起国内外同行的广泛关注。其中，粗糙集著名学者、三支决策理论（Three-Way Decisions）的提出者姚一豫教授将吉林大学课题组提出的多元结构建模和发现方法视为刻画和认知复杂系统/复杂网络微观、中观和宏观三层结构的两个代表方法之一。限于篇幅，下面仅简要介绍有关SBM的两个主要研究进展，以及其科学意义和应用前景。

3.6.1　SBM研究进展

SBM是多元结构发现的核心，在社区发现、多元结构分析、个性化推荐和传播网络建模与推断等研究中都发挥着关键作用。然而，现有的SBM学习算法都采用参数估计与模型选择交替执行的学习机制，时间复杂度过高，最坏情况下达到O(n5)，仅能有效处理数百节点的小网络，如何设计出具有模型选择能力的快速SBM学习算法，使之能有效处理大规模网络，一直是需要解决的问题，该问题是多元结构分析成为主流网络方法的主要障碍。针对该问题，吉林大学课题组深入研究SBM学习的可扩展性，取得了以下两个重要进展。

第一，吉林大学课题组首次实现了SBM的并行学习机制，在保持学习精度和模型灵活性的前提下，大大降低了SBM学习时间复杂度。

SBM中的隐含变量具有相关性，导致其后验分布不能采用模型参数显式表达，只能采用变分技术近似估计，而变分推理过程只能和模型选择交替执行，这是导致SBM参数估计与模型选择难以并行的根本原因，长期困扰着研究者。为解决这一棘手问题，吉林大学课题组创造性地提出了“重参化块学习机制”：通过参数的数学变换消除隐含变量的相关性，使得SBM的模型选择和参数估计在“块”而非“模型”的粒度上并行进行，对评价“不好”的“块”不再进行参数估计并及时消除，对剩余的“块”进行增量式评估，以此方式大大减少模型选择和参数估计“交替”执行的冗余计算，显著降低学习时间。该算法的最坏时间复杂度下降为O(n3)，在当时所有同类算法中运行最快，将SBM能够有效处理的网络规模从几百个节点提高到几万个节点。该学习机制具有一般性，不仅限于网络模型，采用该重参化技巧，还可用于提升其他混合模型的学习效率。

第二，吉林大学课题组提出了第一个符号网络统计学习模型，将统计网络模型的应用领域从一般网络拓展到包含更多语义信息的符号网络。

现实世界复杂系统中的对立关系普遍存在。例如，在人际交往中，个体间可以是喜欢、信任、支持、合作等关系，也可以是憎恶、怀疑、反对、竞争等关系。在基因或神经网络中，基因或者神经之间可相互激活，也可互相抑制。这些对立关系可采用网络连接符号表示。对于符号网络的研究，可帮助我们更好地分析符号网络的功能，发现隐含结构，预测网络动态演化。SBM可用于解析零先验网络的组成结构，但现有SBM都局限于无符号网络，无法处理包含对立关系的符号网络。为此，吉林大学课题组从模型构建、参数估计和模型选择3个方面入手，解决现有SBM难以推广到符号网络的问题，首先提出适用于刻画对立关系的符号随机块模型（SSBM）。与现有方法相比，该模型不仅能有效发现零先验符号网络的多元结构，还比现有方法更好地解决了态度预测和链接预测问题。在人工网络和真实网络上的大量实验结果表明：SSBM模型在无符号网络、平衡网络和非平衡网络上的社区发现和链接预测性能都远远优于现有的方法。

理论上，该工作解决的一个重要问题是SBM的模型选择。在贝叶斯框架下，证据是最理想的模型选择标准，但通常难以计算（需要计算多重积分，时间复杂性是问题规模的指数级），仅仅存在理论上的指导意义。统计网络学习的研究也面临同样的困难。在变分贝叶斯框架下，吉林大学课题组为SSBM提出了具有模型选择能力的学习算法。该工作采用变分贝叶斯EM 估计隐含变量与模型参数的近似分布，并基于这些分布的超参数构造出相对容易计算的证据低边界，代替证据进行模型选择，大大降低了计算开销。该工作以统计网络模型为例，论述了如何通过文中技巧构造证据低边界，使基于证据的模型选择不再被束之理论高阁，而是可被有效计算和应用，为解决模型选择这一机器学习界的理论难题提供了新思路。

3.6.2　小结

现实世界中的网络在形成和演化的过程中往往会受到多种因素的影响，这些因素共同塑造出复杂的网络全局结构。因此，复杂网络多元结构分析是复杂网络研究的基本理论问题，具有非常重要的理论研究意义和广泛的应用前景。本章主要从多元结构建模和发现的角度对其中的一些关键理论问题和研究进展进行了介绍。

统计网络模型（如SBM）是多元结构分析的核心方法，在个性化推荐和网络动力学等应用中都发挥着关键作用。然而，现有的SBM学习算法时间复杂度过高，大大限制了其应用范围。如何设计出具有模型选择能力的高效SBM学习算法，使之能有效处理大规模网络，这是大规模网络多元结构研究面临的最大问题。尽管SBM学习可扩展性的研究取得了一些结果，将能够有效处理的网络规模从几百个节点提升至几万个节点。然而，现实世界中的网络规模通常更大，具有几十万个、几百万个，甚至几千万个节点的规模。现有的SBM学习算法面对这些规模的网络都无能为力。因此，还需进一步开展以下多方面的研究。

研究人员在现有研究成果的基础上，发展新的理论和方法，进一步解决SBM学习面临的可扩展性问题，采用统计网络学习的新技术，如贝叶斯框架下的重参化技术、深度学习框架下的网络表示学习技术，以及基于云计算框架的分布并行处理技术，使能够有效处理的网络规模达到千万级节点。在此基础上，进一步深入开展复杂网络多元结构分析的实证研究，研究不同真实网络中共存于不同尺度上的各种结构模式及其之间的各种复杂关系，探索新的网络结构，进一步深化人们对复杂网络结构的认识，从原理上帮助人们理解并揭示网络结构与网络功能、网络动力学之间的内在联系。

本章编写人员：陈华钧、王元卓、杨博