2.1 复杂网络基本理论

2.1.1 复杂网络理论及发展

追溯发展足迹，网络首先得益于图论和拓扑学等应用数学的发展。图论中的图是由若干给定的点及连接两点的线所构成的图形。它通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。用图论的语言和符号可以精确、简洁地描述各种网络。关于图论的文字记载最早出现在欧拉1736年的论著中。第一个图论问题是著名的哥尼斯堡七桥问题，欧拉证明了这个问题没有解，并且延伸了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。此后，哈密顿问题、四色猜想等有力地推动了图论及拓扑学的发展。1936年，德国数学家Konig正式提出图论思想。20世纪40—60年代，拟阵理论、超图理论、极图理论，以及代数图论、拓扑图论等都有较大的发展。

20世纪50年代末到60年代，匈牙利著名数学家ErdÊs和Rényi建立了ER随机图理论，用相对简单的随机图来描述网络，其重要发现是ER随机图中的许多重要性质均随网络规模的增大而突然涌现。此后近40年，ER随机图一直是研究复杂网络的基本模型。图论不仅为数学家和物理学家提供了描述网络的共同语言和研究平台，而且图论的许多研究成果和方法技巧至今仍然能够自然地应用到社会网络分析与复杂网络的研究中去，成为网络科学研究的有力方法和工具 [134-135]。然而，后来对一些真实网络的研究表明，大多数的复杂系统既非完全规则又非完全随机，单纯应用规则图和随机网络理论无法实质性地研究这些复杂系统，因此需要新的模型来合理描述这些真实网络所显示的特性。

20世纪90年代末期，两项开创性的工作打破了随机图理论的框架：①1998年Watts和Strogatz [4]在Nature上发表文章，提出了小世界网络（small-world networks）模型，也称为WS模型。通过以某个很小的概率切断规则网络中原始的边，并随机选择新的端点重新连接，构造出了一种介于规则网络和随机网络之间的网络，它同时具有大的群聚系数和小的平均距离，称为具有小世界效应的小世界网络。Newman和Watts [136]随后改进了WS模型，提出了NW模型。②1999年Barabasi和Albert [5]在Science上发表文章，指出现实世界中的许多复杂网络节点度分布具有幂律函数形式，由于幂律分布没有明显的特征长度，该类网络称为无标度网络（scale-free networks）。

（1）小世界特性。具有高集聚系数和短平均距离的网络称为小世界网络。对于规则网络的每一个顶点的所有边，以概率p断开一个端点，并重新连接，连接的新端点从网络中的其他顶点随机选择，若所选顶点已与此顶点相连，则再随机选择其他顶点来重连。当p=0时，该网络演变为规则网络；当p=1时，为随机网络；对于0＜p＜1的情况，p存在一个很大的取值区间，在生成网络的同时，拥有高集聚系数和短平均距离，即小世界网络。小世界网络介于规则网络与随机网络之间，实现了从规则到完全随机之间的连续演变，如图2.1所示。它同时具有大的群聚系数和小的平均距离，其度分布为指数分布且峰值取平均值，每个节点有大致相同数目的度；网络平均距离随节点数增多而缓慢增加。研究表明，互联网、万维网都具有小世界的性质。

（2）无标度特性。与随机网络的泊松分布不一致，现实世界中许多复杂网络的度分布遵循幂律分布。幂律分布在双对数坐标系下呈直线，斜率为定值，其分布和网络的规模尺度无关，因此称为无标度网络。无标度网络的节点度分布为幂律形式，是与时间无关的渐进分布，且与系统规模无关；极少数节点有大量的连接，而大多数节点只有很少的连接，这些具有大量连接的节点称为“集散节点”；复杂网络系统的行为主要是由少数关键节点主控。实验结果表明，无尺度网络也具有短平均距离和高集聚系数。

小世界网络和无标度网络的发现，以及随后许多真实网络的实证研究表明，真实网络既不是规则网络，也不是随机网络，而是兼具小世界和无标度特性，使人们认识到各种复杂系统的网络结构可能遵从某些基本法则和普适规律。Watts和Barabási等人的工作得到了学术界的高度认可，大批学者加入到复杂网络的研究行列中，研究从数学和物理学渗透到生物学，以及社会科学、工程技术科学等众多学科，相关应用研究在信息与网络中心战、系统搜索与推荐、疾病传播与控制，以及突发事件预警与处置等方面发挥着重要作用。

复杂网络发展在很大程度上归功于强大的计算设备和迅猛发展的互联网，它使得人们能够收集和处理规模巨大且种类不同的实际网络数据。此外，学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共同性质。值得注意的是，复杂网络的严格定义尚未形成定论。复杂网络这一称谓大致包含三层意思：①它是大量真实复杂系统的拓扑抽象；②它在感觉上比规则网络和随机网络复杂，因为规则网络和随机网络很容易生成，但尚未有一种方法能生成完全符合真实统计特征的复杂网络；③对它的研究有助于理解“复杂系统之所以复杂”这一重要问题。

2.1.2 复杂网络建模、参数和层次

1.复杂网络结构建模

复杂网络的概念和模型具有较强的普适性。实际上，网络结构既是系统存在的普遍形式，又是对系统结构进行建模的重要方式。一方面，作为复杂系统的结构形态或基本框架，复杂网络包含自然界和社会的众多因素，例如神经系统是大量神经细胞通过神经纤维相互连接形成的网络；计算机网络是计算机通过通信介质，如光缆、双绞线、同轴电缆等相互连接形成的网络。另一方面，现实世界中很多自然和社会系统都可以用复杂网络来描述，从大型电力网络到全球交通网络，从社会关系网络到经济、政治网络，甚至语言和软件网络。复杂网络是对复杂系统相互作用的一种本质抽象：系统中的个体对应网络中的顶点，个体间的相互关系对应网络中的边，系统可以表现为由点和边构成的图。网络结构研究的关键问题是依据适当方法，建立能反映实际网络拓扑性质的模型。

（1）邻接矩阵建模。网络可以用矩阵的形式加以描述，邻接矩阵（adjacent matrix）刻画了网络节点之间的连接关系。网络可由邻接矩阵A完全描述：给定邻接矩阵A是一个N×N的方阵，其元素为aij （i,j＝1,2,…,N），若边eij存在，则aij=1，否则aij=0，邻接矩阵的对角线上的元素都是0，即aii=0。不失一般性，网络可表示为G=（V,E），其中V表示网络节点的集合，E表示网络节点间相互关系的集合，并用N=|V|表示网络节点数目，M=|E|表示网络边的数目。考虑边的方向性，网络可分为无向网络和有向网络；考虑边的权重，则可分为加权网络和无权网络，如图2.2所示。有向网络中，边用方向箭头连接。加权网络中，wi表示边的权重。含有环或多重边的网络称为多重网络。

（2）二分图方法。二分图是图论中具有理论意义和实际意义的特殊模型 [2]。在二分图中，所有节点可分成两个集合，且同一集合中的点都不直接相连。二分图可以描述现实世界中广泛存在的“项目—参与者”二分结构。一类节点则是它们参与的活动、事件或者组织，称为“项目”，例如影片、科学论文等；而另一类节点是参与某种活动、事件或者组织的“参与者”，如演员、科研人员等。由于研究更加关心同一类节点之间的相互作用关系，常把二分图向一类节点投影，得到单模式网络，此时每个项目的所有参与者之间都存在表示在此项目中产生相互作用关系的边，而每个项目在投影图中则表示为一个完全图，多个完全图集合成为整个单模式网络，如图2.3所示。

2.复杂网络基本参数 [137]

对复杂网络模型结构描述的基本几何量包括：度、集聚系数、平均路径和介数等。

（1）节点度及其分布。网络中节点i的度指与节点i直接相连的边的数目，即

节点度分布用分布函数p（k）表示，其含义为一个任意选择的节点恰好有k条边的概率。

（2）集聚系数。集聚系数反映网络的群集程度，定义为网络的平均度与规模之比。在网络中，集聚系数的分布反映各个节点附近的边的密集程度，集聚系数的平均值则反映了整个网络中边的密集程度。节点i的集聚系数定义为

式中，Mi为节点i和其ki个邻节点所组成的子网络的实际边数。整个网络集聚系数定义为

（3）平均距离与网络连通性。节点间的距离定义为连接两点的最短路径所包含的边的数目；平均路径长度是指所有节点对之间的最短路径的算术平均值，用来度量整体网络节点之间的通信距离，即一个节点平均经过多少步才能达到另一个节点。令l为一无向网络图G中的平均最短路径长度（距离），则

其中，dij为节点i到j的最短路径（距离），节点与其自身的距离为0。网络连通性最先应用在小世界网络中刻画节点之间流传输的效率。节点i和j之间传输效率反比于它们之间最短路径的长度：εij=1/dij，特别地，当节点i和j不连通时，εij=0。网络整体连通性定义为

3.复杂网络层次特征

复杂系统不可能一次完成从元素到整体的涌现，需要通过一系列中间等级，从元素开始，由低层次到高层次逐步整合、发展，最终形成系统 [138]。在系统的形成、保持和运行上，等级层次结构是复杂系统最合理的、最优的组织形式 [139]。

真实世界中的许多复杂网络，如Internet、万维网、社会关系网络等都具有一定的层次性 [140]。复杂生物网络的近期研究 [141]中发现“全局－模块－模体－个体”层次结构，如图2.4所示。对许多复杂网络，如生物、技术和社会网络的研究表明，其有着共同的全局结构特征，如小世界和无标度性。同时，具有相似全局结构特征的网络反映出极其不同的局部结构特征，通常以一种模块化的方式体现在网络中，模块即由不同性质、类型的多个节点因连接程度相同组成的结构子网络，同一模块内部节点的连接比较稠密，不同模块之间的节点的连接比较稀疏 [142]。实证发现多数网络都存在模块结构，如社会网络可视为由很多熟人群体形成的网络，万维网由大量话题类似的网站群组构成 [143-144]。模块还有它的底层结构——模体，即网络少数节点微观层次相互作用的基本模式。模体结构简单，但其表现的局部性质和网络的构成机制密切相关，复杂多样的网络结构恰恰就是由多个模体相互关联、嵌套形成的。学者在神经网络、食物链和技术网络中找到了各种模体，并体现了不同的动力学功能，如代谢网络和信号传导网络中的模体具备生物化学过程及信号传递作用。

4.复杂网络层次

生命复杂网络按照个体、模体、模块到全局四个层次组织，被认为是生命网络中各层次的最优结构与组织形式。从生物学角度来看，模体是指生物网络中的基本功能团 [145-147]；而从计算角度来看，模体是相对于随机网络而言，在真实网络中频繁出现的子图。同样，从生物学角度来看，模块也是指生物网络中的功能团；而从计算角度来看，模块是模体簇或者是生物网络中稠密的子图。

作为生物网络中的功能单元，模体和模块具有紧密的联系。目前关于模块的发现有许多成果 [148]，研究表明功能上具有紧密联系的基因和蛋白质可以由生物网络模块推导出来 [149-150]。由于目前许多简单生物，如酵母的大部分基因和蛋白质的功能是未知的，设计可靠的方法通过已知基因和蛋白质的功能来预测未知元素的功能是当前生物学研究的前沿 [151]。作为个体和模块之间的网络基本拓扑结构，模体能从局部刻画网络链接的模式并识别网络拓扑结构和动态特性，从而能够全面分析网络结构性质及网络功能，是刻画网络基本结构的重要概念。