复杂网络与机器学习融合的研究进展

李泽荃 杨 曌 刘 嵘 李 靖

1(华北科技学院管理学院 北京 101601) 2(华北科技学院安全工程学院 北京 101601) 3(华北科技学院计算机学院 北京 101601)

0 引 言

复杂网络和机器学习分别是统计物理学和计算机科学领域内重要的研究方向。复杂网络是研究复杂系统的一种角度和方法，它主要关注系统中个体相互作用的拓扑结构，以及网络上物质、能量、信息的动力学传播过程，是理解复杂系统性质和功能的基础[1]。机器学习主要指计算机利用已有的经验来获得学习能力的一种计算方法，通过从大量的数据特征中获得数据的表示方法，以自动的方式模拟人类专家的判断[2]。

近年来，将复杂网络和机器学习结合起来进行研究分析引起了越来越多学者的关注。从本质上说，主要包括两个方向：一是研究基于复杂网络理论(或图论)的机器学习技术；二是利用机器学习算法来挖掘复杂网络拓扑结构背后隐藏的信息和知识。对于前者，自然界中以网络形态存在的数据无处不在，利用网络方式进行数据表示有其内在的优点，它能有效地捕获数据的空间、拓扑和功能关系，获得更高的机器学习算法准确度；而对于后者，人类社会的进步促使各类系统越来越复杂，相对应网络的规模急剧增大，借助智能数据分析工具，如各类机器学习算法，有助于解决复杂网络中模型与知识的有效挖掘问题。

到目前为止，人们根据所研究的具体问题，提出了多种多样的基于网络的机器学习方法或复杂网络分析工具，并做了一些总结和探讨[3]，但仍不够全面。关于复杂网络与机器学习融合的研究图景，未来将有更多可能。

1 复杂网络简介

在自然界中，从技术到生物直至社会各类系统都可以通过复杂网络加以描述，其中节点表示个体或组织，边表示它们之间的关系[4-7]。对真实网络进行实证研究不仅有助于认识网络行为、改善网络性能和有效地管理网络，而且能够先于理论发现现象，为进行理论探索打下基础，或者作为理论应用范围的重要判据[7]。为了更好地利用复杂网络，我们对其数据结构的复杂性和节点及其相关连接的多样性进行了统一。

1.1 网络演化模型

为了研究真实网络的拓扑结构，学者们提出了许多网络模型，其中有一些网络模型由于其广泛的应用价值而得到了重点关注，例如随机网络[8]、小世界网络[9]、随机聚类网络[10]、无标度网络[11]和核心-边缘网络[12]。

1.1.1 随机网络

1959年，Erdös和Réyni[8]首次提出了随机网络的概念。随机网络模型中任意两个节点以某一概率相连，不考虑节点之间的空间关系和相似性。即随机网络中有V个节点，节点之间的连接概率为p，节点的度分布服从二项分布(V-1,p),表示为：

(1)

其他更多特性可参考文献[13-15]。

1.1.2 小世界网络

一些现实世界的网络表现出很强的小世界性，即节点经过少量的几步(边)就可以到达另一个节点，如在社会网络中，可以经过一个很短的连接与世界上任意一个人产生联系[9,16]。文献[9]介绍了小世界网络的形成方法：在包含V个节点的规则网络中，每个节点与k个节点相邻，每条边以概率p任意随机连接到另外一个节点。当p=0时，网络不发生重新连接，仍然保持为规则网络；当p≠0时，所有的连边将在概率p下重新连接，随着p值增加，网络的小世界属性越来越显著；当p=1时，网络成为随机网络，此时网络中节点度数分布的峰值接近2k[9,16]。图1为网络在概率p下重新连接的示意图。

图1 WS小世界重连边模型

网络的小世界特性最直接的理解是在这种网络上信息传播的速度非常迅速。

1.1.3 无标度网络

1998年，Barabási和Albert[11]发现某些网络中的极少数节点拥有很高的度值，而大部分节点只有很小的度值，即极少数节点与非常多的节点连接，而大部分节点只和很少的节点连接。基于这一发现，1999年他们提出了一种新的网络模型，即无标度网络，网络中节点的度分布服从幂律分布。无标度网络结构中关键节点或度数较大的节点更容易与新节点相连，从而形成更多的连接，新节点也有与度值更高节点相连接的“偏好”。

网络的无标度性与网络受到攻击的鲁棒性紧密相关，这种层次结构具有一定的容错能力。关于无标度网络对随机攻击具有很强的鲁棒性而对蓄意攻击极为脆弱的特点，Cohen等[17-18]和Callaway等[19]利用渗流理论对其进行了详细研究。

1.1.4 随机聚类网络

一些现实世界的网络如社会网络和生物网络呈现出模块化的结构特性，文献[10]把它们称为社团，属于同一个社团的节点有许多相互连接的边，而不同的社团间的连接相对较少，这类网络被称为随机聚类网络。

在随机聚类网络的形成过程中，两个节点如果属于同一个社团，它们连接的概率为pin，如果属于不同的社团则连接的概率为pout。典型的随机聚类网络中，pin值较大，pout值较小，即社团之内的节点连接紧密，而社团之间的节点连接稀疏。当pin值较小，而pout值较大时，网络中节点的聚类效果不显著。基于以上参数，定义Zin/和Zout/分别为社团内节点和社团间节点的连接程度。或许，随着Zout/值的增大，社团间的连接逐渐紧密，社团之间的界限也将越来越模糊。

1.1.5 核心-边缘网络

核心-边缘网络结构最早出现在社会学[20-21]、国际关系学[22-23]和经济学[24]等学科中。一般认为网络中的核心节点是具有很大度数的节点，识别核心-边缘结构最常用的定量方法是由博尔加蒂和埃弗雷特于1999年提出的[12]，按照该方法，对某一网络进行聚类分析时，对于其中的关键节点，采用不同的社团检测算法可能使它们分配到不同的社团[25]。因此，如何判断它们与不同社团之间关系的强弱至关重要，可以采用社团重叠算法[26]。在这种情况下，一般意义上的社团概念可能并不能很好地实现对中等尺度网络实际结构的理解，将关键节点划分为核心结构来考虑可能更为合理[27]。可以将单个社团看作网络核心结构的一部分，整个核心结构由多个社团组成，社团之间可以存在重叠[28-29]。

1.2 网络度量方法分类

根据复杂网络的统计特性，如度、度的相关性、距离和路径、网络结构以及网络中心性等，众多学者已经提出了许多网络相关统计描述计算方法。按照在计算中使用信息的类型，可以将其分为三类：

1) 局部算法：仅仅根据节点自身的信息来进行计算。

2) 混合算法：除了根据节点信息外，还利用其直接和间接邻域内节点的拓扑信息进行计算。这些信息可以是最简单的局部拓扑，如邻域中的三角形数，也可以是网络的全局信息，如最远两个节点之间的最短路径等。

3) 全局算法：根据整个网络拓扑结构进行计算。

图2描绘了这三类网络统计度量方法相互关系的示意图，表1列出了常用的各类网络统计描述。

图2 网络统计度量方法分类

表1 复杂网络常用的统计描述

1.3 复杂网络的动力学过程

1.3.1 随机游走

随机游走是一系列由连续随机步组成的轨迹的数学表示[30]。它常被用来描述很多自然现象和工程问题，如图形匹配和模式识别[31]、图像分割[32]，神经网络模型[33-34]、网络中心性度量[35]、网络划分[36]、通信网络构建与分析[37-38]等。

给定一个网络G=和一个起始节点v∈V，随机选择一个邻居节点，移动到该邻居；然后，再次随机选择这个新节点的邻居并移动，以此类推，以这种方式选择节点的随机序列就是网络上的随机游走过程。如果网络是加权网络，可以与连边权重Avu成正比的概率过渡到邻居u。

本质上，网络上的随机游走和有限离散马尔可夫链的原理基本是相通的，所以网络上的任意一个离散马尔可夫链都可以被认为是一个随机游走过程。众所周知，离散马尔可夫链是随机过程，其未来状态在条件上独立于过去的状态，因此只要知道当前状态即可求得未来状态。在图论中，图的节点可以表示状态，因此，步行者从节点v移动到其邻居节点的概率独立于步行者的过去轨迹。

1.3.2 惰性随机游走

平稳分布只适用于非周期网络，如果网络具有周期性，就需要引入惰性随机游走算法。惰性随机游走算法可以被看作是网络中经典随机游走算法的改进版，仅将网络G中的每个节点u添加自身环即可[39]。

游走过程中，在时刻t，游走者面临两个不同的选择：它可以根据转移矩阵以1/2的概率过渡到相邻节点；或者，以1/2的概率停留在当前节点。因此，从形式上看，惰性随机游走的概率分布p(t)的演化可以表示为：

(2)

式中：P′(t)为转移矩阵，有：

(3)

1.3.3 自避行走

网络自避行走指网络中所有节点仅被访问一次所获得的路径。自避行走最早在聚合物化学理论中出现[40]，此后其特性也引起了数学家和物理学家的广泛关注[41]。从广义的角度看，自避行走通常被考虑为无限格子上的算法，所以每一次移动只允许在离散的方向上进行并且具有一定的步长。可以看出，自避行走不是马尔可夫过程，因此需要利用过去的轨迹来计算出其可能出现的未来状态[41]。

1.3.4 游客漫步

游客漫步可以理解为一个游客在P维地图中游览景点(数据项)的问题。在每个离散的时间步，游客遵循一个简单的确定性规则，即游览最近的景点，且该景点在之前的步没有被游览过[42]。游客漫步不同于自避行走，前者是一个确定性过程，而后者是一个随机过程。游客的行为在很大程度上取决于景点(数据集)的结构和起始景点。在计算方面，游客的行动完全通过邻域表来实现，其中邻域表是通过对与特定景点相关的所有数据项进行排序而构建的。一般情况下，每个游览路径都可以看成两个阶段：初始瞬态和周期循环(吸引子)。

在大多数与游客漫步相关的文献中，游客可以访问记忆窗口μ以外的其他景点[42-44]。随着μ值增加，游客有可能在数据集上进行长距离跳跃，因为在时间范围内邻居最有可能已经被完全访问。在分类任务上，可以采用网络的方法来避免该问题，此时游客仅被允许访问与其相连的节点(景点)。或许，当值很大时，游客很可能被困在节点上，而不能进一步访问其他邻居节点。

1.3.5 流行病传播

复杂网络上的流行病传播已经引起了众多研究者的关注，大家主要关心的是网络结构如何减弱或放大疾病传播。由于流行病传播过程可以看作是信息传播，因此对于机器学习来说非常有用。目前主要有两种流行病传播模型，SIR和SIS模型[45-47]。关于其详细综述，请参阅文献[48-50]。另外，对于一些复杂网络上信息传播的研究进展，可参见文献[51-58]。

2 机器学习简介

机器学习的目标是让计算机拥有人类的“学习”能力[59-64]。传统的机器学习方法有三种类型：第一种是监督学习，它主要利用已标记的样本数据进行训练得到数学模型，再利用该模型对未知数据进行预测[61,65-67]。第二种是无监督学习，其主要任务是利用样本的相似性或拓扑结构学习和发现样本的内在联系[63,68-69]。其中，监督学习和无监督学习的主要区别在于监督学习利用包含外部标记信息的数据进行训练得到函数，而无监督学习没有任何标注数据，主要将某种属性相似的样本聚集在一起。第三种方法叫半监督学习，它是监督学习和无监督学习相结合的一种方法[70-72]，半监督学习中少量的样本数据带有标记，而大多数样本数据是未标记的，学习过程就是利用这些少量已标记样本对其他未标记样本进行标记和分类。图3是机器学习的三种范式。

图3 三种类型的机器学习方法

值得一提的是，机器学习领域中的新技术，即深度学习。其主要利用由多个非线性变换构建的高阶数学模型来表达样本项之间的关系，通过利用高效的算法进行分层特征提取，从面部识别等实际应用来看，深度学习的一些方法将使机器学习任务变得更为容易。

2.1 监督学习

仅利用具有标记信息的样本数据进行训练和建模的算法称为监督学习。通常我们利用监督学习来预测无标签样本的类型标签，其中，对离散值进行预测称为“分类”，而对连续值进行预测称为“回归”[59]。

监督学习主要分为两个阶段：训练阶段和分类阶段[59,66-68]。在训练阶段，利用带有标签的样本集合训练得到分类函数；在分类阶段，利用上一步得到的分类函数对未标记的测试集进行标记分类。关于监督学习的详细数学描述可参见文献[59,63,68,73]。对于监督学习的主要算法，请详见文献[74-80]。

2.2 无监督学习

从本质上来看，无监督学习是分析样本分布的概率密度函数[70]。无监督学习算法可以归纳为四类：聚类[10,81-84]、异常检测[85-86]、降维[87]和关联分析[88]等。聚类是根据样本特征进行分类，通常假设一个相似函数来判断样本之间的同质性或异质性，分类后同一类别应具有尽可能高的同质性，而类别之间则具有尽可能高的异质性[63]。异常检测的目标是找出原始样本中与其他样本属于不同类别的样本项[85]。降维是指采用某种映射方法，将原本属于高维空间中的样本点映射到低维空间中，从而简化样本之间的关系[87]。关联分析简单地说是寻找样本数据间的隐含关系[87]。关于无监督学习的详细数学描述可参见文献[59,63-64,89-91]。

无监督学习最常见的任务是样本聚类，这些集簇可以是某种形状、某种类型的点或对象等[59,90-93]。随着数据量和数据种类的指数增长，提高数据的自动理解和处理能力是重点，例如在数据挖掘、文献检索、图像分割、生物分析、模式分类等任务中，通常我们仅仅掌握很少量的先验信息[91-92,94-96]，因此，其应用非常广泛。

2.3 半监督学习

自然界中存在许多半监督学习的实例。如婴儿通过听到声音到学会说话的过程，期初，婴儿并不了解听到的声音，婴儿的反应仅是记住这些声音，这便是标记的数据，通过不断地刺激和学习，婴儿最终实现了从听到说的能力[97-98]。半监督学习可以有效减少标记样本的工作量，特别是当数据标记成本高昂且耗费时间。关于半监督学习的详细数学描述可参见文献[70-72]。半监督学习应用的领域包括视频索引、音频信号分类、自然语言处理、医学诊断、基因数据处理等[70,72]。

对于半监督学习，数据的一致性假设是前提[99]。通常情况下，半监督学习中存在一个或多个基本假设，包括聚类假设、平滑假设和流形假设[70]。

一般情况下，可将半监督学习算法归纳为四类，即生成模型[70,72,89,100-101]、聚类和标记模型[102-103]、低密度区域分离模型[70,72,89,104-105]和基于网络(图)的模型[80,90-92]。

3 基于复杂网络的机器学习方法

在过去的几年里，基于复杂网络的机器学习方法越来越受到关注。该方法有其内在的优点，即数据通过网络的形式来表征能有效捕获数据的空间结构、拓扑结构和功能关系。该类型的数据通常以网络形式表示，其中一部分节点被标记，另外一些节点未被标记，算法的任务是预测未标记节点的标签。同样，按照机器学习的分类，下面重点讨论基于网络的监督学习、无监督学习和半监督学习技术。

3.1 网络构建技术

在机器学习的很多领域，数据样本点之间的局部关系以及由局部信息衍生出的全局结构经常用网络来表示。在处理机器学习或者数据挖掘的问题时，网络构建是一个非常有必要的步骤。当应用基于网络的机器学习方法分析向量表示的数据样本时，该步骤变得尤为关键，需要采用网络构建技术将输入样本集形成网络。一般来说，按照网络构建过程中的信息类型将网络构建方法分为三类，即局部信息方法、远程信息方法和全局信息方法，详细情况见表2。

表2 网络构建技术分类

3.2 监督学习方法

对于网络环境下的监督学习分类问题，通常利用外部信息(如标签)来训练模型。与一般的监督学习类似，学习过程通常分为两个阶段：训练阶段和预测阶段。训练阶段，模型根据带标签数据样本进行学习；预测阶段，利用模型对未知数据样本进行预测。基于网络的监督学习算法仍然研究的不多，主要有关联图分类算法、关系分类算法和启发式分类算法。

3.2.1 关联图分类算法

关联图分类算法中，应用最多的是k-关联图算法[114]。k-关联图分类算法同样也是将训练集数据构建为网络，即有向k-关联图网络。该算法是建立在基于向量形式的数据集上，主要是将向量数据抽象为节点和连边。在给定的k值构建k-关联图后，在训练和测试阶段都应对网络中的每个子图进行纯度检验用于确定最佳的网络分类。k-关联图中的连边根据修正的k-近邻算法确定。在这种特殊网络形成过程中，只有具有相同标签或类的节点才允许相连，算法模型根据这个简单规则逐步形成整个网络。

网络中子图纯度的定义为：给定参数k值，利用修正的k-近邻算法形成网络，每个节点最多可以具有2k个连接。由于网络为有向网络，每个节点度的取值范围为[k，2k]。纯度测试确定了每个节点的度取值的可行性区间。本质上，它量化了同一类别节点间有效创建的连边数量与每个节点可能连接的总连接值2k之间的比值。因此，网络中某一组件α的纯度φ定义为：

(4)

为了得到最佳k-关联图，具体步骤是从k的最小取值开始逐一计算各个子图。对每个k值和网络子图分别计算纯度值，然后比较由不同k值产生的k-关联图。获得最佳k-关联图之后，学习过程进入具体的分类阶段。在这一阶段，文献[114]采用了贝叶斯分类器进行分类。

3.2.2 集合推理算法

集合推理算法处理的数据与传统监督学习方法处理的数据不同，它规避了数据的独立性假设，因为数据的标签不仅依赖于数据本身属性，同时也依赖于邻域数据的标签[115]。因此，对于网络数据，一个数据项(节点)的标签可能对与之相关节点的标签具有一定的影响。

在网络环境下以相互关联的方式来推断相关节点标签的算法中较为著名的是集合推理模型[116]。与传统的分类技术相比，这种方法可以显著地减少错误分类[117]。集合推理模型可以同时使用数据属性和数据关系特征来进行分类。众所周知，节点的标签也可能与网络上与之间接相连节点的标签相关，同时对所有节点的标签信息进行计算可能更有意义。

另外，在一些学习过程中的特定阶段也可以采用集合推理算法。例如朴素贝叶斯或关系概率树等算法，采用局部分类器预测每个未标记节点的标签，并进一步使用如Gibbs抽样[117]或ICA[118]等集合推理算法重新修改节点的标签，这类方法为局部方法。另一种方法使用全局算法，主要以优化全局目标函数为目标进行训练，这类算法包括循环信念传播和松弛标记法等[119]。

关于集合推理算法，文献[120]提出了一种基于网络的监督学习模型框架(NetKit)。该框架主要由三部分组成：一是局部分类器，主要利用训练集来形成概率分布模型；二是关系分类器，也是估计样本的概率分布，但与局部分类器不同的地方是它考虑了网络中相邻节点关系的影响；三是集合推理器，利用模型对样本类别进行预测。

此类方法已经在各个领域获得了广泛应用，如生物学中分子用途的分析[121]、科研论文链接的分类[118]、链接预测[122]等。再比如在社交网络中预测当前没有关联的两个点在未来某一时间连接的可能性[123]，创建一个小连通子来中模拟社交网络中两个节点之间的关系[124]。

3.2.3 启发式分类算法

文献[125]首次提出启发式分类算法，该算法结合了“网络环境下的易访问性”来执行分类任务。易访问性的衡量标准是基于马尔可夫链理论中的极限概率而确定的。首先，一组标记数据被映射为网络的节点。因此，该网络可以看成是一个离散的马尔可夫链，每个节点代表马尔可夫过程中的一个状态。当对未标记样本进行分类时，因为未标记样本的偏差信息应被考虑在内，包含标记样本的网络中连边的权值需要重新计算。在得到修正的极限概率后，未标记样本的类标签由最容易(易访问)获得的标记样本表示，最终，这样的偏差信息将逐步改变网络结构。

(5)

3.2.4 集成方法

文献[126]提出了一种基于低级分类器和高级分类器的集成方法。从本质上讲，低级分类器是根据样本标签和样本的统计特性进行分类，它可以是任何传统的分类技术，如决策树、支持向量机、感知机、贝叶斯学习，或k-近邻等；而高级分类器除了使用样本的标签外，还使用样本的网络拓扑结构或模式信息进行分类。集成方法的一个突出特点是跨网络技术，即它将输入数据看作一个整体构建网络，并考虑到网络的全局模式。定义集成方法F，它是两种分类器的凸组合，即：

(6)

关于集成方法中高级分类器的构建，目前有两种方法。第一种是平均度、聚类系数和同配性三种网络统计量的结合方法[126]，覆盖了网络从局部到全局的所有信息。其中，度可以准确度量网络中节点的局部信息；聚类系数通过计算当前节点及其邻域内的两个节点所形成的三角形数量度量网络的局部结构；同配性不仅考虑当前节点及其邻域内的节点，而且考虑第二级邻域内的节点(邻域的邻域)、第三级邻域内的节点等。

第二种利用了随机游走过程中的动力学特性[127]。与经典的网络统计量计算方法不同，该算法利用网络中随机游走过程的动力学特性提取网络的高级信息。换句话说，随机游走可以理解为在高维数据空间中随机访问数据节点的过程，通过不断调整随机游走过程中记忆窗口的长度，来提取从局部到全局的网络信息和网络特征。当随机游走的记忆窗口较小时，提取网络的局部结构特征；随着记忆窗口的逐渐增大，游走过程被迫逐渐远离起点，从而学习网络的全局特性。

3.3 无监督学习方法

众所周知，无监督学习任务中样本数据没有类别属性的先验知识。基于网络的无监督学习方法类似，学习过程首先根据相似度标准从输入数据构建网络，再通过网络结构完成知识的学习。无监督学习的一个主要任务是数据聚类问题，实际上，一旦原始数据集转化为网络，数据聚类可以被认为是社团检测问题。众多学者业对于此问题提出了近似的、有效的解决方法，其中包括谱方法[128]，基于介数的算法[129]，模块化贪心优化算法[130]，基于Potts模型的社团检测算法[131]，同步方法[132]，信息论方法[133]和随机游走[134]。

3.3.1 基于介数的算法

识别网络中社团的自然策略是检测并删除连接不同社团节点的连边，以便社团最终彼此断开。在这种情况下，网络单元的数量代表了社团的数量。这是分裂算法的思想，其关键就是寻找社团之间连边的专有特征，从而进行识别。目前最为流行的是基于介数中心性的算法，首先由Girvan和Newman[10,129]提出，在选择要删除的连边过程中，算法根据边介数中心性来确定。在计算时，他们考虑了测地线、随机游走和流三种边介数。如果网络中存在层次结构，原始的Girvan-Newman算法准确度将下降，为此，有学者把模块度最大化算法加入了网络分区的最优划分过程中[129]。Chen和Yuan[136]认为在边介数的评估中考虑所有可能的最短路径可能会导致分区不平衡，即社团大小完全不一致。为了克服这个问题，他们建议只计算非冗余路径，即那些端点互不相同的路径。

3.3.2 模块度最大化算法

模块度是用来衡量网络中一个特定区块划分质量的方法[137-138]，或者用于衡量网络区块划分为模块(也称为组、聚类或社团)的能力。一般来说，其范围为0到1之间的数值。当模块度接近0时，表明网络没有划分出社团结构，认为网络中的边是随机连接的。随着模块度增加，社团结构越来越显现，社团内的连边比例逐渐大于社团间。模块度定义为：

(7)

式中：E表示网络中边的总数目；Aij表示节点i与j之间的连边权重；ki、kj分别表示节点i和j的度；ci表示节点i的社团；1[ci=cj]为指示函数，当ci=cj，为1；否则，为0。

第一个提出模块度优化方法的是Clauset等[137]，随后又有其他学者陆续提出一些改进方法[139-143]。Clauset算法的主要思路是在网络社团划分过程中加入了贪婪算法，即在模块度最大化的每个时间步，选择合并两个能使模块度增幅最大的社团，即找到最大的模块度增量。但该算法有一个缺点，即社团的不平衡问题，计算过程中会产生包含大部分节点的超社团。为解决社团划分的不平衡问题，加速社团合并过程运行时间，出现了Louvain方法[139]，它能够处理百万节点的网络，是迄今为止最快的模块度优化算法。

3.3.3 谱分析方法

图谱分析关注的是图的属性，如其特征多项式、特征值和与邻接矩阵或拉普拉斯矩阵相关的特征向量。首先考虑采用谱分析方法来计算图切割的是Donath和Hoffman[144]，也是他们首先采用图的邻接矩阵特征向量来发现社团的。此后，用于计算和分割图的谱分析方法越来越受到关注[145-147]。例如Zhou等[146]计算了含有任意度和社团结构的随机网络的谱特征。桂春等[148]在Ahn方法[149]的基础上提出了边图谱分析算法，并应用到边社团发现上，进行了兼顾层次性和重叠性的社团检测研究，实验结果表明该算法实现了网络的重叠社团检测并且社团划分结果比较满意。

3.3.4 基于粒子竞争机制的算法

粒子竞争模型的演化与众多自然和社会现象进化过程非常类似，例如资源竞争、动物领地争夺、竞选活动等。Quiles等[150]将此演化过程引入到社团检测问题中，通过研究网络环境下多个粒子的竞争机制来识别社团。由于竞争效应，粒子要么处于活跃状态，要么处于沉寂状态。每当粒子处于活跃状态时，它会同时受到两种相互正交的游走规则的引导，这两种规则分别为随机游走和优先游走。随机游走是一种无条件规则，它只依赖于网络拓扑结构，控制粒子在网络中的探索行为；相反，优先游走是粒子通过强化它们已经占领的节点来完成粒子的防御行为。这些粒子以占领新节点为目标在网络中自主运动(随机的或确定的方式)，同时也试图守卫它们已占领的领地。至此，定义一个转移矩阵用来控制粒子游走到下一个状态的概率分布：

(8)

随后，Silva等[151-152]在粒子竞争过程中考虑了随机非线性动力学机制，提出了形式化的数学表达式，并在手写数字和字母聚类数据集(USPS、MNIST、LR)上进行了测试，达到了非常好的效果，具体见表3，平均排名第一。关于网络中重叠节点或结构的检测，文献[153]利用重叠度进行了分析，他们通过粒子竞争过程中产生的控制水平矩阵对重叠度进行了重新定义，并在扎卡里空手道俱乐部网络、海豚社交网络和《悲惨世界》的人物关系网络进行了计算，所得结果比传统方法更准确。

表3 多种算法的数据聚类结果比较

3.3.5 变色龙算法

变色龙算法常用于数据聚类问题[159]。它是一种层次聚类算法，其在识别相似社团时采用了互连性和近似性特征。网络完成构建之后，变色龙方法通过最小化边割将网络划分为多个社团来发现网络的初始分区。在找到子群之后，该算法通过使用社团相似性度量准则(社团间的相对互连度(RI)和相对近似度(RC))来重复组合这些子群。这两个指数定义如下：

相对互联度:

(9)

相对近似度：

(10)

最终，变色龙算法将高RI和RC值的社团对进行合并。也就是说，它选择连接性强的而且紧密结合的社团。该算法非常适合用于大数据样本的计算，但在高维数据上，表现不尽人意[160]。

3.3.6 基于群体动力学的算法

群体行为是由大量简单的个体通过互相作用呈现出宏观复杂的组织系统[161-162]。目前，群体行为技术已经被成功用于解决各种优化问题[163]，如De Oliveira等[164-165]将群体动力学模型引入到网络中的社团检测研究。社团检测算法的思路分为两个步骤：1) 将数据样本转为化网络形式;2) 在构建的网络上检测集群或社团。计算时，最初将整个网络视为一个大社团，然后逐步分解为小社团，直到每个节点对应一个社团。迭代过程中，关键的因素是更新规则，在该算法中节点按照圆形组织，给定初始随机角度θi(t=0)，节点角度的更新规则按以下公式来定义：

(11)

式中：N(vi)为节点vi的邻居节点集，ηi(t)为vi在时间步t的移动速率，Aij为邻居vj对邻居vi的影响权重。

由于该算法具有层次性结构，因此可以使用树状图来描述计算结果。例如，Oliveira[166]利用此算法在海豚社会网络上进行了仿真计算，所得结果如图4所示，图中节点的虚实表示它原有所属社团。

图4 文献[59]中的海豚社会网络社团检测结果

3.3.7 同步方法

近年来，物理学家越来越关注复杂系统多样性的动力学特性，一些学者也进行了大量的耦合振荡器的实证分析[166-167]。实际上，这些系统内单元同步的涌现与单元之间交互的拓扑结构密切相关，随着时间的演化，这些动力学模型呈现出不同的模式，而这些模式与复杂网络中社团的层级组织有着内在的联系。理解同步现象最成功的尝试之一来自Kuramoto[168]，他提出的相位振荡器耦合模型非常适合用来仿真各类同步模式。

网络环境下，每个节点都可以看作是一个振荡器，连边权重则表示不同振荡器之间的耦合强度。有些文献已经发现高度相互关联的振荡器集合更容易与那些稀疏连接的振荡器同步[168-171]。因此，对于具有重要连接模式的复杂网络，从随机初始条件开始，那些形成局部社团的高度互连的单元将首先同步。随后，越来越大的网络结构采用同样的形式继续演化，直至达到最终状态。此状态下，所有的节点都具有相同的相变过程，只要有明确的社团结构存在，该过程会在某个时间尺度上产生。因此，拥有全局吸引子的动力学过程揭示了不同的拓扑结构，而且这些拓扑结构可能表示的就是网络社团。在Kuramoto模型的基础上，Wu等[171]将一种无连边节点的负耦合作用考虑在内，建立了同步过程的动力学演化模型，即：

Aij)sin(θj-θi)

(12)

式中：V表示网络的节点数目；ωi表示第i个节点的固有频率；Aij表示节点之间的耦合关系；θi和θj分别表示节点i和j的相位；Kp和Kn分别表示正负耦合强度。

3.4 半监督学习方法

在诸如视频识别、声音信号分类、文本分类、医疗诊断以及其他应用领域中，很容易找到海量的无类标签的样例，但需要使用特殊设备或经过昂贵且用时非常长的实验过程进行人工标记才能得到有类标签的样本，由此产生了极少量的有类标签的样本和过剩的无类标签的样例，也就产生了半监督学习[172]。而在基于网络的方法中，网络的拓扑结构是将标签从已标签节点向未标签节点传播的主要引擎。近年来，关于用复杂网络理论来研究半监督学习取得了重要进展，将这些方法进行分类，主要包括最小割算法[173]、局部和全局一致性算法[174]、局部和全局正则化[175]、半监督模块化[176]、判别式游走[177]、随机游走[178-179]和标签传播技术[180-181]等。

3.4.1 最大流与最小割算法

最大流和最小割算法最初用在二分类问题中[182]。半监督学习的分类方法可以看作是一个图分割问题。在二分类问题中，正标签被看作是源点，负标签被看作是汇点。算法的目标是找到一个最小边的集合来阻断从源点到汇点的流量。被分割后的图中，连接源样本点的将会被分类为正样本，而连接汇点的样本将会被分类为负样本。因此，损失函数可以写为：

(13)

最大流与最小割算法有很多有趣的特性[183]，可以采用网络流工具进行多项式的时间计算，学习过程也可以被视为马尔可夫随机场过程。或许，该算法也存在一些缺陷，如它是不存在置信区间的硬分类问题。为解决此问题，文献[184]引入了基于谱划分的方法，可以在图中产生近似的最小割比率。

3.4.2 高斯随机场与调和函数

为解决最小割算法的硬分类问题，有学者提出了高斯随机场与调和函数方法[173,181]。该方法被视作是最近邻方法的一种变种形式，其中最近邻的标注样本在图上用随机行走的方式计算。另外，调和函数根据邻近节点标签的加权平均数来估计未标注节点的标签。同样，它可以看作是一个平方损失函数，已标记的数据样本标签是固定的，然后加上一个拉普拉斯正则项。因此，损失函数可表示为：

(14)

3.4.3 局部全局一致性学习

局部全局一致性学习算法是基于网络的半监督学习技术中最早的方法之一[174]。该算法通过构造标记样本与未标记样本结构的足够平滑的分类函数来进行学习。损失函数定义如下：

(15)

近年来，国内的研究人员也对局部全局一致性学习算法进行了研究。针对文献[174]提出的算法分类精度在很大程度上取决于控制参数的合理设置问题，王雪松等[185]提出了一种少参数的简洁算法；另外，在标签传递过程中，他们仅将未标记样本的标签根据相似度传递给近邻，而将已标记样本的标签强制回填，确保了标签传递源头的准确性。为降低计算复杂度，白本督等[186]提出一种K-均值构图法，主要将稀疏表示理论应用到基于图的半监督学习过程中，通过稀疏分解稀疏矩阵来得到图中邻接矩阵和边权重。

3.4.4 附着法

(16)

3.4.5 相互作用力算法

受自然界中物体之间存在吸引力的启发，Cupertino等[189]提出相互作用力算法来进行网络的半监督学习。它将数据样本模型化为一个P维空间上的节点，并根据施加在它之上的合力执行相应的运动。已标注数据样本充当吸引点，而未标注样本获得吸力并朝这些吸引点移动。一旦一个未标注样本足够接近已标注样本，比如说半径，那么吸引点的标签就传播到位于其周围的未标注样本上。同时，未标注样本从标注节点接收标签，然后成为新的吸引点。通过反复迭代，所有的数据样本都会收敛到某个吸引点，完成标签的传播过程。

3.4.6 判别式游走算法

判别式游走(D-Walks)算法在文献[177]中有详细介绍。从本质上看，D-Walks算法依赖于网络上的随机游走过程，该过程可以被看作是马尔可夫链，网络中的每个节点对应于马尔可夫链的一个状态。另外，D-Walks算法需要计算节点介数，未标注节点被分配到介数最高的类别。介数的大小可以按下式计算得到：

(17)

3.4.7 随机竞争-合作学习

(18)

式中：i和j表示网络中的节点，vk表示粒子k的父节点。

随后，Wu等[192]又将该算法应用于错误标签传播的预防上。众所周知，真实世界中，由于仪器误差或人为标注的失误，错误标注样本在数据集中常见。如果这些错误标签被用来进一步分类新数据(有监督学习)或传播到未标记样本(半监督学习)，可能会产生严重后果。通过模拟计算，该算法在真实数据集上的表现优于线性传播算法(LP)[193]和线性邻域传播算法(LNP)[194]。

4 基于机器学习的复杂网络信息挖掘

如前所述，对于复杂网络，我们主要关注的是其统计特征、拓扑结构及关键节点和连边。随着数据量的急速增加，网络变得越来越大，单纯地网络分析方法已经难以满足网络信息快速挖掘的需要。这促使部分学者开始从事计算机技术用于分析复杂网络的研究，特别是近年来人工智能技术的快速进步，给机器学习和复杂网络的交叉应用提供了思路。如在社会网络、生物网络等领域，已有研究人员利用机器学习算法进行了网络信息挖掘的尝试。

4.1 网络统计特征提取

在神经科学领域，大脑网络中神经元(可看作为网络节点)之间是否存在同步特征通常由脑电图(EGG)和脑磁图(MEG)记录的时间序列来评估。为区分正常人与阿尔茨海默症患者，Roberto H等[32]建立了机器学习分类模型，并且考虑了五种特征选择方法，即近似熵、样本熵、多尺度熵、自动互信息和Lempel-Ziv复杂度，通过在EGG和MEG数据上进行测试，前两种方法获得了非常好的分类结果，特别是样本熵方法能有效地减少对信号长度的依赖。另外，大脑网络中不同区域的功能连通性也是研究热点，传统的网络同步度量方法仍存在检验盲点[195]。Zhang等[196]基于静态的和视频刺激下动态的fMRI(功能性磁共振成像)数据得到的大规模功能性连接模式进行了分类试验，并且在连通性测量时考虑了Pearson相关系数、偏相关系数、互信息和小波变换相干性四种指标，结果表明小波变换相干性度量标准在分类任务中性能最优。

在对网络进行二值化时，一般根据连边权重的相关规则来修剪图，如删除权重低于给定阈值的连边，这类阈值的确定相当困难，或许，机器学习的方法可以优化此过程。Massimiliano Z等[197]提出了利用机器学习分类模型来选择阈值的方法，并将获得的分类结果作为二值化网络的阈值，或许，该方法只能解决单阈值问题。而对于多阈值问题，Jie等[198]提出了一个基于功能性连接网络的分类框架，主要应用多个阈值来对不同级别的区域进行编码，随后利用基于图核的递归特征消除方法选择最相关特征，以及利用支持向量机算法建立分类模型，在识别正常人与阿尔茨海默症患者时分类准确率可达91.9%。

4.2 网络拓扑结构分类

自闭症症状的早期筛查有助于及时发现患者，通常的做法是进行正常人和疑似病例的大脑功能性连接模式对比。文献[199]基于Granger因果关系的脑连通性数据，运用支持向量机和Fisher准则进行了连接模式的分类，并对由邻接矩阵构成的各类特征进行排序，进而确定使网络分割函数达到最大值时的最佳子集，计算结果表明，基于邻接矩阵和图论方法的组合分类模型可以达到87.5%的准确度。Matthew D S等[200]在进行抑郁患者与正常人的分类模型构建时，采用了一种新的特征评估方法，即运用迭代分类器的分类性能来评估所选特征的鲁棒性。另外，文献[198]进行分类模型构建时采用的是多核SVM算法，认为网络拓扑特征的提取和连边权重阈值的选择可以同时进行。

4.3 网络关键节点和关键边识别

在分析大脑网络映射功能时，通常采用模式识别方法检测多体素模式，为解决维数多的问题，Federico D M等[201]采用基于多特征选择的机器学习算法(递归特征消除算法RFE)进行功能性成像数据分类任务，即通过支持向量机算法递归地消除不相关的体素来识别关键节点。Rodolphe J等[202]提出使用正则化树来进行fMRI数据节点选择的方法，该方法基于先前选择的树节点中的变量构造的函数来惩罚当前的节点，这使得整个预测结果变得更加鲁棒和精确。在生物信息学领域，一个核心任务是根据基因表示谱推断出基因调控网络，一般来说，该方法面临的主要问题是样本少而维数大。为解决此问题，通常利用训练数据之外的先验知识(网络拓扑结构)来获得统计规律，Fabricio M L等[203]将基因调控网络的无标度特性加入到一个经典的特征选择方法中，称为序列浮动前向选择算法(SFFS)，它从完整的网络开始，并根据目标函数(自顶向下方法)消除最少相关的节点，重复这个过程直到满足停止条件为止。

在社会网络分析领域，节点排序是一个核心任务。根据复杂程度的不同，节点重要程度度量分为局部度量和全局度量。Jeh等[204]提出了一种估计两个节点相似度的度量标准，主要通过随机游走计算这两个节点到它们所连接的相似节点的度数。除了静态图上的节点排序，一些学者[205]还研究了动态图上的节点排序，考虑了利用诸如电子邮件等事件的时间信息来追踪节点随新事件发生的排序变化情况。

一旦网络形成，就可能面临选择代表网络结构的连边子图问题，因此，通过过滤无关的连边来选择关键信息的方法对于获得简单的相关子图是必要的。从数据挖掘的角度来看，目前主要采用的方法为互信息。代表性的方法是由Adam A[206]提出的ARACNE算法，主要用于检测和删除网络中的非直接连边，算法核心是在给定互信息阈值的情况下，通过分析网络中每组三节点连边，迭代删除低于阈值的连边。另外一种方法是利用玻尔兹曼熵最大化原理，由Lezon T R等[207]提出，其主要思想是以最小程度依赖于缺失信息的形式来完成统计学习。

4.4 网络节点分类

在具有连边的节点分类问题中，连边的属性与结构有助于节点分类任务。Lu等[208]对每个数据样本增加新的属性，使其能够处理基于链接的节点分类问题，扩展了机器学习分类器的应用范围。Bhagat等[209]基于局部和全局的链接结构相似性算法对博客进行标注，完成分类任务。Sen等[210]研究了网络数据样本的集体分类方法，比较了四种常用的推理算法在模拟数据和现实数据上的分类性能。Backstrom等[211]通过分析社团进化过程来刻画网络中个体位置的结构特征，并成功用于节点的分类中。

5 重点关注的两类问题

综上所述，复杂网络与机器学习有相似的目标，给定一些数据，通常表示一个复杂系统，目的是从其挖掘一些信息，并创建一个新的知识表征(拓扑结构或者机器学习模型)。目前，复杂网络与机器学习交叉应用的可能方向主要体现在社团检测与聚类、链路预测和语义表征等。

5.1 聚类与社团检测

机器学习中的聚类与复杂网络分析中的社团检测是两个具有较多相似性特征的问题。大多数聚类算法仅利用样本间相似性(距离)的局部信息，而复杂网络方法允许网络的全局拓扑结构包含在算法当中，因此计算结果更加准确。如图5所示，左侧的聚类任务中，虽然节点A与节点B更相似，同属于一个类别，却划分到其他类别中；而对于右侧的社团检测任务，虽然节点A更接近三角形社团，但因其与节点B有连边存在，所以社团划分合理。

图5 聚类与社团检测问题的对比[212]

可以看出，在聚类任务中引入复杂网络理论能有效地提高计算准确度。目前来看，该方法在不同研究领域都有所应用。在网络音乐领域，Joan S等[213]采用社团检测算法检测同一首歌曲的覆盖类别和范围，其结果由于传统聚类算法。经济物理学中，在金融市场交易的投资者集群被确定为统计校准网络中的社团[214]。或许，某些情况下聚类算法也可以用于进行复杂网络中的社团检测，例如复杂网络中重叠社团结构识别的模糊c-均值聚类算法[215]、社团检测的自适应聚类算法[216]、重叠和非重叠社团结构识别的模糊聚类算法[217]。

5.2 链路预测

链路预测已经成为复杂网络中一个重要的研究方向，特别是在生物网络和社会网络。同样在数据挖掘领域，推荐系统与之对应，也是计算机技术中的主要研究方向之一，研究思路和方法基于马尔可夫链和机器学习。尽管它们在实质上是等价的，但仍旧是在不同的研究路径上前行，仅有个别的研究人员在联合方向上进行了尝试。

6 结 语

众所周知，现实世界中，几乎所有的系统都可以采用网络的方式来描述，复杂网络就是以网络的视角去分析这些数据，找出可被解释的结果或者现象，相当于挖掘隐藏在数据背后的规则；对于机器学习，我们主要研究如何使计算机从给定的数据中学习规律或模型，并利用学到的模型进行预测。从本质上来说，复杂网络和机器学习的目标是一致的，都是为了挖掘数据内在的规律，两者的融合将有更多突破。

可以看出，融合复杂网络理论和机器学习技术已经是众多学者开始着手研究的领域。随着诸如大数据、人工智能等技术的出现，要想让它们发挥更大的作用，需要在理论层次和技术层次上更进一步创新。我们总结了在该交叉领域未来可能成为研究热点的几大问题，希望在不久的将来，这些问题能够得到完美解决。

首先，从有益于促进复杂网络研究效率的角度看：

(1) 优化复杂网络统计度量指标。随着大数据时代的到来，数据集越来越大，如大型在线社交网络，对网络的度量变得越来越复杂，尤其是从计算成本的角度来看，耗时耗力。如果按照这种趋势发展，复杂网络的各类度量指标将不得不依靠机器学习技术进行重新优化设计，在具体设计时应特别关注其计算成本，以确保其可扩展到数亿的节点。

(2) 开发用于复杂网络分析的软件平台。数据的规模性和复杂性将迫使研究人员需要设计开发新的软件工具和机器学习模型来管理和分析这些数据集。虽然在这个方向上已经采取了一些措施，例如创建图形数据库等，但是大多数解决方案仅限于可视化的思路，忽略了真实世界网络的复杂性。

另外，从有益于强化机器学习理论背景的角度看：

(1) 提升机器学习算法准确度。如实际应用中，通常样本特征的提取过于简单、解释性差，使用复杂网络理论去挖掘潜在的可被解释的规律，再融合群体智慧知识，然后构建相关数据特征，按照这样的思路去解决机器学习任务视为最优路径。

(2) 扩展机器学习模型数学理论。由于大量缺乏标注样本，或者人工标注成本过高，我们越来越依赖半监督学习技术，但是半监督技术理论的不完善限制了其广泛应用。或许，从复杂网络领域可以寻找可能，如利用复杂网络上的流行病扩散动力学过程来完成半监督学习中数据标签的传播。