Ch9 二分网络与多层网络

第9章

二分网络与多层网络9.1二分网络9.2多层网络12二分网络非常适合于描述两类对象之间的关系，例如，人与他们参加的活动、作者与他们撰写的论文，或者顾客与他们购买的商品等。而多层网络是一种更为复杂的网络结构，它允许同一个节点在不同的层次上以不同的身份或状态存在。在多层网络中，节点之间的连接可以是同一层内的（内部连接）也可以是跨越不同层次的（外部连接），这种结构可以更好地捕捉现实世界中系统的多维性质和复杂性。本章将简要介绍二分网络和多层网络的概念、网络结构特性以及动力学过程等。9.1二分网络39.1.1二分网络的概念4二分网络是由两类节点以及它们之间的连边组成，同类节点之间不存在连边。它是复杂网络的一种重要的网络表现形式，许多实际网络具有二分性。4种典型的二分网络：科学家合作网络、听众与歌曲网络、演员合作网络、图书借阅网络。9.1.1二分网络的概念5科学家合作网络

科学家和论文形成了一个二分网络，纽曼将这个二分网络投影到单顶点网络进行研究，若两位科学家合著过论文，则这两位科学家之间就有一条连边，这属于无权投影。他收集了几个不同学科的科学家合作网络，统计了每个网络的统计量，并首次统计了这些科学家合作网络中每个作者文章数的分布和每篇论文的作者数分布。另外他提出了一种将无权投影变成加权投影的测定合作强度的方法，该方法得到的科学家合作网络的连边是带有权重的。9.1.1二分网络的概念6听众与歌曲网络研究了人们从网上下载音乐的数据，建立了一个二分网络：网络中的两类节点分别是听众和歌曲，如果听众曾下载过某些歌曲，这个听众和这些歌曲之间就存在连边。他们发现，歌曲的听众规模符合幂律分布，而听众所听歌曲的规模符合指数分布。为了探索该网络的结构，他们设计了一种聚类方法——PIB法，分别对听众和歌曲进行聚类。9.1.1二分网络的概念7演员合作网络标志着复杂网络研究热潮的开始的两篇经典文献都以好莱坞演员合作网络为例证。该演员合作网络是一个由演员和影视作品两类节点所组成的二分网络。参考文献集中研究了好莱坞演员合作网络的小世界特性和无标度特性。可见，演员合作网络是十分重要的实证系统。刘爱芬等对中国大陆近80年的电影网络进行了实证研究，通过采用二分图及其投影来描述大陆电影合作竞争网络，并得到了平均距离、距离分布等统计性质。9.1.1二分网络的概念8图书借阅网络把读者作为一类节点，把图书作为另一类节点，当某位读者借阅过某本书时，就在这两个节点之间连接一条边，这样就构建出了图书借阅系统的二分网络模型。傅林华等研究了根据北京师范大学图书馆外借处的14个月内的图书借阅情况所建立的二分网络，发现这个网络体现了很好的单标度性质。王进良等也对2005年北京师范大学的图书借阅记录进行分析。9.1.2二分网络的投影9

从二分网络到单顶点网络的投影方式有多种，可分为无权投影和加权投影两类。

二分网络可以用二分图

来描述，其中

代表一类节点，代表另一类节点，E为上述两类节点之间的连边。对一类节点，进行无权投影时的规则是：如果两个同类节点有至少一个公共邻居，那么这两个节点之间有连边。无权投影所得网络只能给出一类节点之间是否存在边，而无法描述节点之间的合作强度。9.1.2二分网络的投影10二分网及其节点投影结果图9.1.2二分网络的投影11对于二分网络的多种加权投影方法的区别主要在于对权重的设定不同。最常见的一种方式是把权重定义为两个同类节点共同连接的另一类节点的个数。这种简单的加权投影比无权投影保留了更多的信息。纽曼提出合著过论文的两位科学家的熟识程度不仅受其合作次数的影响，还受合作所拥有的参与者总数的影响。周涛等认为边权应该是不对称的，因为几名合作者对于他们的合作关系紧密程度的贡献的估计是不同的。9.1.2二分网络的投影12

二分网的两类节点的简单加权投影9.1.2二分网络的投影13周涛等指出认为边权应该是不对称的，并且在传统的二分网络投影过程中，只有一条连边（即度为1）的节点在投影后会消失，他们提出了一种新的加权投影方法。二分图中位于上面的节点初始分配的资源为x，y和z。首先将这些资源分配到下面的节点上去，分配原则是将资源平均分配到和自己相连的所有节点上。接着将位于下面的节点上的资源平均分配到上面的节点上去。9.1.2二分网络的投影14二分网上的资源分配过程示意图矩阵有两个特点：不一定是对称的；对角元素非零。9.1.3二分网络的基本拓扑性质15度和度分布

在二分网络中，虽然有两类节点，但由于度考虑的是单个节点的属性，因而二分网络中度的定义与其他类型的网络没有本质的区别。二分网络中一个节点的度是指与该节点连接的边的数量，两类节点的度值之和相等。度分布定义为随机选择一个节点，它具有k条连边的概率。可以用分布函数来表示整个网络度的统计特征。实证研究发现，二分网络的一类或两类节点的度分布也符合幂律分布9.1.3二分网络的基本拓扑性质16

集聚系数

二分网络中某一节点的集聚系数定义：

林德等给出了基于四元组的集聚系数定义，他认为某一点的集聚系数等于该点实际存在的四元组的个数与该点可能存在的四元组的个数之比：9.1.3二分网络的基本拓扑性质17

当要考虑

i的集聚系数时，需要把节点i的所有对一级近邻贡献的结果的分子和分母分别求和后再求比值：

两个同类节点共同连接的异类节点数占它们连接的所有异类节点数的比例：9.1.3二分网络的基本拓扑性质18

9.1.3二分网络的基本拓扑性质19

最短路径长度

在单顶点网络中，两点的最短路径定义为所有连通这两点的通路中所经过节点最少的一条或几条路径。比较单顶点网络上最短路径的定义，同样可以定义二分网络上的最短路径长度。一种定义就是把二分网络看成普通的单顶点网络来计算其最短路径长度。这种定义的缺点是没法区分二分网络和单顶点网络的差别。9.1.3二分网络的基本拓扑性质20

介数

在单顶点网络中，点介数的含义为网络中所有的最短路径中经过该节点的数量。有了二分网络最短路径的定义后，就可以得到点介数。类似地，二分网络点介数的定义也可以推广到边上，即最短路径经过某边的次数。纽曼等发现，单顶点网络的边介数可以应用于网络的聚类分析。那么，同样可以将二分网络的边介数用于二分网络的聚类分析。9.1.4二分网络的社团结构21

二分网络的社团结构也可以根据连接的相对疏密程度来定义[13]：社团可以看作二分网络中的一组节点，使得社团内部异质节点间的连接比较密集，而社团间的异质节点间的连接比较稀疏9.1.4二分网络的社团结构22

基于边集聚系数的社团划分算法计算网络中所有边的集聚系数值，并计算网络模块化的值；找到并删除集聚系数值最小的边，如果集聚系数值最小的边不止一条，那么随机选择其中的一条删除，并计算删除边后网络模块化的值；重新计算剩余边的集聚系数值；重复前三步，直至找到网络模块化的局部最大值。将这种断边方法应用于实际网络和人工生成的二分网络中，发现当社团结构比较明显时能够得到比较好的结果。9.1.4二分网络的社团结构23

9.1.4二分网络的社团结构24

9.1.4二分网络的社团结构25优化模块化函数算法

吉梅拉等在提出二分网络中模块化定义后，给出了3种算法：无权投影算法、加权投影算法以及二分算法。

无权投影算法不可靠，常常得出错误的结论；只关注一类顶点的划分时，加权投影算法和二分算法的划分准确率都比较高，而且划分出的结果相似，但是对于模块结构不明的二分网络，二分算法优于加权投影算法9.1.5二分网络的演化模型26模型分类：一类模型生成的二分网络是静态的，即节点和边的数目是固定的，只是存在边的重连；另一类模型生成的二分网络是动态的，除了存在边的重连，节点或边的数目也在不断变化，新增的边按一定的规则连接网络中的节点。

纽曼等提出了一个生成随机二分网络的静态模型：给定两类节点的度分布，在节点度值的限定下任意连接它们之间的连边。9.1.5二分网络的演化模型27

一些动态模型陆续被提出。这些模型的不同主要在于连接新增边的规则不同。例如，拉马斯科等将巴拉巴西和阿尔伯特提出的偏好依附特性引入动态模型中，即网络中新增的边按偏好依附的规则来连接，使得生成的二分网络具有无标度特性。还有一些研究关注“重连”的二分网络模型，例如，考虑到社团结构和重连在二分网络中十分普遍，还提出了一种带有社团结构的二分网络模型，来研究重连对度分布的影响。9.2多层网络2829

多层网络是复杂网络研究的前沿和热点，它突破了单层网络中节点和连边同质性的限制，考虑了多种类型节点及其连边关系

。

已有的多层网络研究在理论上主要关注网络的拓扑结构、动力学、功能以及它们之间的关系，同时在社会经济系统、生态和生物系统等领域进行了应用。

本节重点从多层网络建模、基本统计性质、社团结构、多层网络功能与动力学行为等几个方面对多层网络的研究进展进行梳理与评述。

虽然多层网络概念没有明确的统一定义，但是依据拓扑结构特征可将其划分为多路复用网络、时序网络、网络的网络、相互依赖网络等不同的类型。9.2.1多层网络模型构建30

一个含有M层的多层网络可以用超邻接矩阵一个含有M层的多层网络可以用超邻接矩阵

来表示。

多层网络中层的邻接矩阵集合：

层间网络邻接矩阵的集合：

多层网络的一般形式可以被定义为：9.2.1多层网络模型构建31多层网络用超邻接矩阵可表示为：多层网络和网络的网络示意图：9.2.1多层网络模型构建32相互依存网络

由多个具有相依存关系的网络所组成。层间连边表示了节点的依存关系，这种依存关系使得一个网络层的动态变化会极大地影响其他网络层。9.2.1多层网络模型构建33多路复用网络

所有网络层由同一组节点构成。该网络的特点是每一个网络层表示节点间的某种关系或者相互作用模式，而层间连边表示同一个节点在不同网络层的对应关系。9.2.1多层网络模型构建34时序网络

多层网络还可以用于研究单个网络随时间演变的情况。在随时间演变的过程中，节点和连边都有可能发生变化(新增或移除)。在此，由单个网络随时间变化所构成的多层网络被称为时序网络9.2.1多层网络模型构建35多层网络的张量表达

张量的阶表示为张量维度的数目。一阶张量是一个向量，二阶张量是一个矩阵，三阶以上的张量称为高阶张量。

以多路复用网络为例，该类型多层网络的张量表达是

这是一个四阶张量。

多层网络的张量表达不仅可以直接得出不同层之间的对应关系，还不会丢失网络的细节信息。

9.2.1多层网络模型构建36多层网络的聚合表达

不考虑多层结构层间交互性质的情况下，将多层网络压缩成单层网络(该单层网络被称为聚合网络)。

聚合网络是多层网络的简化形式。这样的建模方式虽然降低了后续研究的难度，但是丢失了多层网络特有的拓扑信息(层间相互作用关系)。9.2.2多层网络的拓扑性质37多层网络的基本统计特征节点的统计特征：

度

重叠度

点强度辛普森多样性指标

香农熵9.2.2多层网络的拓扑性质38网络层的统计特征：

层的重叠性

层的度相关性

每个层度序列之间的相关系数

集聚系数2-triangle三角形数和1-triad三元数的比例3-triangle三角形数和2-triad三元数的比例9.2.2多层网络的拓扑性质39多层网络中心性测度多层网络的节点中心性：

一方面，以预先确定的恒定权重作为层对节点中心性影响的权重；另一方面，着眼于一些特殊的多层网络类型定义中心性，如多路复用网络。PageRank节点中心性不仅仅取决于指向该节点的邻居数量和质量，还取决于所在层的相对重要性。9.2.2多层网络的拓扑性质40多层网络的层中心性：

每一层网络在多层网络中的相对重要程度。

层中心性定义目前有两种比较常用的方法：一是通过张量分析方法量化其重要性；二是根据层内拓扑结构信息量化其重要性。张量分析方法张量迭代方程：9.2.2多层网络的拓扑性质41基于层内拓扑信息量化层中心性

两种策略计算层中心性：边的介数中心性和最短路径。该指标的核心思想是承担全局连接越多的网络层具有越高的中心性。具体来说，首先将多层网络压缩成聚合网络并量化边的重要性；其次根据某些策略将边中心性分布到每一层，最后将层中心性定义为层内边的中心性之和。

融合层与节点的信息以确定层中心性和节点中心性的算法：基本思想是如果一个节点能够连接到影响力较高的层，则具有更大的中心性，相应地，如果网络层中高中心性的节点越多则该层越具有影响力。9.2.3社团结构42基于模块度优化的社团划分算法

模块度函数优化是探测社团结构的经典方法，其核心思想是通过最大化目标函数获得最优的社团划分结果。

多层网络社团结构具有代表性的研究是2009年发表在“Science”上的论文。该文将模块度的概念推广到多层网络，其核心思想是通过比较最大化实际网络中边的总权重与作为零模型的随机图中边的期望总权重之间的区别，以此将网络分为若干个不同的社团。具体来说，首先将网络中的每个节点都视为一个社团，并在多层网络模块度函数最大化的约束下合并社团，其次不断重复这个过程，直到模块度函数达到一个局部最大值。9.2.3社团结构43基于网络层聚合的多层网络社团划分算法

两种思路：聚合网络社团划分算法和共识社团划分算法。

聚合网络社团划分算法：将一个多层网络压缩成单层网络后，直接利用单层网络的社团划分算法对其进行社团探测。该方法的明显缺点是忽略了层相互作用的异质性。

共识社团划分算法：利用每个网络层的社团划分结果和节点相似性矩阵进行聚类分析。具体来说，首先对多层网络的每个层进行社团探测，其次根据每个节点对(i,j)在同一层网络中属于同一社团的次数与网络层数的比值定义节点之间的相似性，最后基于节点相似性的聚类分析方法获得最终的社团结构。9.2.3社团结构44基于动力学的社团划分随机游走方法

局部自适应随机游走算法，通过调整转移概率，使其依赖任意给定节点和网络层之间的拓扑相似性。首先，该方法定义了一个节点

在下一时刻呆在原位置

，跳到同一层的邻居节点以及跳到其他层的同一节点

和不同节点

处的概率。其次，基于多层随机游走的长度定义了距离矩阵。该矩阵包含层内和层间任意一对节点之间的所有可能距离。无论两个节点是否在同一层中，当这两个节点属于同一社团时，它们之间的距离较小；反之距离较大。最后，对距离矩阵进行聚类。9.2.3社团结构45压缩流方法

有助于捕捉加权和有向网络中的社团探测。通过随机沃克模型对动力学建模证明了该方法可以揭示具有更多重叠的、更小的模块。在该模型中节点的转移概率为：9.2.3社团结构46多层网络中的重叠社团划分节点同时属于多个社团的现象被称为社团结构的重叠性。派系过滤算法：多层网络的派系过滤社团划分方法分为3部分：1)定义多路复用网络层的派系。AND-派系是由各个层次的派系组合而成的，即--AND-派系为具有

k个节点的多层网络中的子图，该子图包括来自

m个不同层的至少

m个不同-团的组合。2)通过AND-派系定义找到最大派系及其派系邻接矩阵。3)聚合派系。当两个派系至少共享

k-1个节点和

m条边时，则将这两个派系聚合在一起，进而得到最终的社团结构。9.2.3社团结构47边聚类算法：

多层网络社团结构可以通过由许多不同类型的连边构成，利用边聚类社团划分的思想可以量化节点间连边的相似性进而探测多层网络的重叠社团。

重叠社团探测算法。该社团划分算法的步骤主要分为：首先，计算同一层和跨层边的相似性。其次，计算多层网络社团密度。最后，通过连边相似权和树状图社团密度，并根据最大密度和聚类分析找到网络的社团。9.2.4多层网络功能48多层网络的鲁棒性与渗流多层网络的鲁棒性：

多层网络中节点与连边的多样性会影响系统的鲁棒性及其动力学过程。实际网络经常面临各种突发事件的干扰，使网络崩溃与瘫痪，甚至遭受经济损失。深入探讨网络拓扑结构对鲁棒性的影响，将有助于更好地了解实际网络的鲁棒性能，进而设计具有抗毁性的网络结构。9.2.4多层网络功能49网络类型对多层网络鲁棒性的影响

相互依存网络中，减少网络之间的耦合强度会导致渗流在临界点附近从一级相变转为二阶相变。

通过在层之间增加额外的连边会提高系统的鲁棒性。

考虑多层网络的层次结构对鲁棒性的影响。结果表明层次结构可以影响基础设施网络的脆弱性。

基于沙堆模型分析了无标度性质和层间关联度如何抑制多层网络中节点的大规模失效。9.2.4多层网络功能50不同类型的层间相关性对多层网络鲁棒性的影响

层间的度相关性对鲁棒性的影响：研究表明在随机攻击的情况下正相关的多层网络比负相关的网络更加健壮；相反，在蓄意攻击的情况下正相关网络具有脆弱性而负相关网络则具有鲁棒性。此外，多层网络中层间的入度(出度)相关性增加了网络的鲁棒性。

多层网络潜在的几何相似性对鲁棒性的影响：多层网络潜在的几何相似性会缓解网络目标攻击的脆弱性。

非最大连通集团中的节点被激活所带来的影响：随着网络层间依赖关系的增加，系统鲁棒性的边界也会随之提高。9.2.4多层网络功能51网络社团结构对多层网络鲁棒性的影响

多层网络不仅具有相互关联层间耦合结构，还具有社团结构。网络在特定区域发生局部故障时，社团结构对影响整个系统发挥着重要作用。社团结构的变化会给耦合系统带来极端的风险。而对于每层网络中具有相同的社团数量且层间连接被限制在不同层对应的社团之间。结果表明模块化结构会显著地影响相变的类型。9.2.4多层网络功能52多层有向网络的不对称性对多层网络鲁棒性的影响

基于生成函数和渗流理论的理论框架分析相互依赖的有向网络的鲁棒性：每层网络不对称性增加了多层网络的脆弱性并呈现混合相变。更为重要的是异质网络比同质网络更具鲁棒性。此外，有向多层网络中巨强连接组件比巨弱连接组件更容易受到攻击。

基于不需要跟踪每个级联步骤的自洽概率方法分析了有向依赖边对临界性的影响：多层网络的相变性质只能由几个参数来决定，且节点间有向依赖关系大大降低了网络的鲁棒性。

在有向多层网络中，层间的耦合强度会使系统呈现不同的相变现象。9.2.4多层网络功能53多层网络的渗流

多层网络中一些节点的故障会导致从属节点以及其他层节点的故障，这种级联故障破坏了网络连接性质，最终会导致系统突然崩溃。一个重要的问题是如何控制失效节点的比例以避免系统的功能性失效。该问题可以用渗流方法进行建模与模拟，进而分析系统的脆弱性。9.2.4多层网络功能54从网络结构的视角讨论多层网络的渗流

通用框架研究相互依存网络的渗流特性：结果表明层间耦合强度q能够影响系统的相变。在渗流的过程中存在最大的耦合强度

和有效的耦合强度

：当

时，多层网络有二级相变；当

时，则呈现出混合相变。这里混合相变是指序参量在临界点有不连续的跃变和临界指数关系；其他情况下不存在相变现象。渗流的临界阈值不取决于网络的层数。

量化多层有向网络的不对称性对网络鲁棒性的影响：结果表明了多层有向网络的不对称性会增强级联故障的鲁棒性。9.2.4多层网络功能55

从节点的空间地势差异的视角讨论3D网络拓扑结构的渗流理论。道路网络一个小的局部扰动可能导致整个道路网络在临界点处的大规模系统故障。

考察了具有层次结构的多层网络的渗流过程。层次结构的弹性取决于每一层社团结构的数量、节点度、移除节点的比例以及层间的耦合强度。

关注了多层网络的迭代渗流过程，即探究历史依赖机制的作用。连续渗流相变可能由若干过程迭代作用而成。而无限迭代渗流过程会改变系统巨分支的涌现方式，进而呈现出不连续相变。9.2.4多层网络功能56多层网络上的最优渗流

最优渗流指的是在复杂网络中如何移除尽可能少的节点以最大程度破坏渗流过程中的最大连通集团，从而将连通集团分裂成许多小规模且相互断开连接的集团。

将该思路拓展到多层网络，重点关注在最优渗流过程中忽略多层结构所产生的后果。如果忽略层的存在会高估系统的鲁棒性。

通过耦合网络的灾难性崩溃与活跃节点的动态消亡过程展示了网络之间的相互依赖的最佳范围。9.2.4多层网络功能57群体渗流和键渗流

实际系统中一些节点会以群组的形式相互协作以增强其抵御风险的能力，但是在无法抵御风险时，这些相互协作的节点会同时失效。这一现象被