复杂网络研究综述：一种描述复杂关系的结构_复杂网络理论

对复杂网络一个简单的总结，不足或错误之处还请多多指教。

复杂网络研究综述：一种描述复杂关系的结构

摘要

复杂网络是由数量庞大的节点和它们之间错综复杂的关系共同构成的复杂网络结构，其拓扑结构特征具有高度复杂性。在数学领域，复杂网络表现为具有独特特性的图。这些特性在简单网络结构，例如晶格网络、随机图等中并不存在，却在现实世界的网络结构中频繁出现。复杂网络的研究是当前科学研究中的一个热点领域，与现实世界中各类高度复杂性系统如网际网络、神经网络和社会网络的研究有着密切的联系。
关键词： 复杂网络 无标度 小世界 路径长度 聚集系数

引言

复杂网络理论的发展源于图论的相关研究。在图论中，图通常是由一组顶点和一组连接两顶点的边构成的图形，这种图形通常代表某些特定的关系。例如，在著名的柯尼斯堡七桥问题中，欧拉将每座桥视为一条边，边所连接的地区视为顶点，从而证明了七桥问题无解。这种将实际问题数学化表达并分析的方式，逐渐发展为图论。
随着研究对象越来越复杂，图中的顶点数目与边数目逐渐增加，逐渐形成了网络的概念。然而，传统的网络有时并不能充分描述大量真实复杂系统，因此复杂网络的概念逐渐演变。
复杂网络理论在多个领域得到了广泛应用，包括在线社交网络平台、社区探测、交通运输等。随着复杂网络的快速发展，其已经成为研究各种复杂系统的重要工具。

复杂网络的基本概念

关于复杂网络的概念，还没有给出一个统一的定义。目前流传最广的一个定义是钱学森定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络。在研究网络时，人们通常将符合某些特征的网络称作复杂网络。

度分布

一个图由若干顶点和连接这些顶点的边组成。每个顶点所连接的所有边的数量称为该顶点的度。度分布是描述复杂网络中顶点度数的总体分布的指标。在随机网络中，顶点的度数符合泊松分布的概率模型，当顶点数量很大时，随机网络的度分布将接近于正态分布。然而，在真实的网络中，少数顶点通常具有较大的度，并随着多项式速度递减，这种分布符合幂律分布。因此，通常将满足这种分布的复杂网络称为无标度网络。

平均网络长度

网络中的距离通常定义为两个顶点之间的最短路径的边的数量。网络的直径是指网络中任意两点之间距离的最大值。平均路径长度又被称为特征路径长度或平均最短路径长度，它是网络中两点之间最短路径长度的平均值。平均网络长度反映了网络的紧凑程度，即网络的大小。在20世纪中期，米尔格拉姆通过实验发现，两个随机选择的人之间的信件传递的平均路径长度约为5.56，这后来被称为“六度分离”。这个实验表明社交网络比我们想象的要小得多。在复杂网络领域，学者们发现许多真实网络的平均路径长度远小于人们的想象，这一现象被称为“小世界效应”。

聚集系数

一个网络节点的邻居节点之间连接的数目与这些邻居节点之间可能存在的最大连接数目的比例，称为该节点的聚集系数。而整个网络中所有节点聚集系数的平均值，即为该网络的聚集系数。聚集系数用于描述网络中顶点的聚集情况，即网络的紧密程度。例如，在一个交通网络中，某个机场的直达机场很可能是其自身的直达机场，或者某个机场的直达机场之间也可能相互为直达机场。聚集系数可以通过顶点三元组来描述，一个节点三元组指的是三个节点，这三个节点要么通过两条无向边相连（开三元组），要么通过三条无向边相连（闭三元组）。
全局聚集系数的定义为：
闭三元组的数量/所有三元组的数量
显然，只有在每个顶点都与其他顶点相互连接的全连通网络中，聚集系数才能等于1，一般情况下小于1。

介数中心性

在图论中，介数中心性是基于最短路径的一种针对网络中顶点中心性的衡量标准。对于全连接网络图，其中任意两个顶点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个顶点的介数中心性即为这些最短路径穿过该顶点的次数。介数中心性在网络理论中有广泛的应用：它代表了某顶点与其他顶点之间的互动程度。 介数中心性也分为边介数和顶点介数，反映了相应的顶点或边在整个网络中的作用和影响力。例如，在通信网络中，一个有更高介数中心性的顶点在网络中有更强的控制能力，因为更多的信息传递时将通过该顶点。 介数中心性被用为对中心性的一种常见测量方式： 它适用于解决网络理论中的许多问题，包括与社会网络、生物、运输和科学合作等方面相关的问题。
在图论中，介数中心性是一种衡量网络中顶点中心性的标准，它基于最短路径的概念。对于全连接网络图，任意两个顶点之间都存在至少一个最短路径，这些路径的长度可以通过计算路径上边的数量或边的权重来得出。每个顶点的介数中心性等于这些最短路径穿越该顶点的次数。这个指标在网络理论中有广泛的应用，可以反映一个顶点与其他顶点之间的互动程度。
介数中心性分为边介数和顶点介数，分别反映了相应的边和顶点在整个网络中的作用和影响力。在通信网络中，具有较高介数中心性的顶点在网络中具有更强的控制能力，因为更多的信息传递将经过该顶点。
介数中心性是一种常见的中心性测量方式，适用于解决网络理论中的许多问题，包括与社会网络、生物、运输和科学合作等方面相关的问题。

网络弹性

网络的弹性亦被称为网络的鲁棒性或者网络的脆弱性。网络作用的基础就是顶点之间的连通性，当网络中的顶点被随机删除或者有选择地删除时，网络的平均路径长度会有较大的变化，即会对网络的连通性产生影响，即网络弹性。随机删除的方式被称为鲁棒性分析，有选择删除的方式被称为脆弱性分析。如有学者通过对随机网络模型（度分布服从指数分布）和BA网络模型（度分布服从幂律分布）进行研究，结果发现随机删除基本不影响两类网络的平均路径长度；有选择地删除会使BA网络的平均路径长度有相较随机网络更快的增长。这说明度分布满足幂律分布的网络鲁棒性较强，但比较脆弱，这就是因为网络中存在着一些度数较大的顶点，即介数中心性较大的顶点。

典型的复杂网络模型

大量复杂网络由于其所具有的不同特征：如度分布、平均网络长度等而被分为多种具有规律的模型。

规则网络

规则网络是最简单的网络模型之一，其特点是每个顶点的邻居顶点数据都相同。如全连通网络、一维链网络、正方形晶格网络等。其特点是平均网络长度大，聚集系数大。

随机网络

随机网络是指在N个顶点构成的网络中，网络中的边完全是以一定概率连接两个顶点形成的，节点的度分布近似为泊松分布。其特点是平均网络长度小，但聚集系数很小。

小世界网络

小世界网络是指具有小世界效应的网络。小世界网络是复杂网络模型中一类特殊的结构，这种网络中的顶点大多并不相连，但绝大部分顶点只需几步就可到达，即其平均路径长度很短。在现实生活中，大多数的真实网络具有小世界性（平均网络长度小）和聚集性（聚集系数大）。
理解小世界最著名的一个实验就是米尔格拉姆的“六度分隔理论”实验，在这个实验中，他将一些信件交给自愿的参加者，要求他们通过自己的熟人将信传到信封上指明的收信人手里，他发现，296封信件中有64封最终送到了目标人物手中。而在成功传递的信件中，平均只需要5次转发，就能够到达目标。也就是说，在社会网络中，任意两个人之间的“距离”是6。由此可见规则网络和随机网络并不能很好地展现真实网络的性质，这也印证着真实网络既不是完全确定的，也不是完全随机的，即真实网络介于完全确定与完全随机之间。
小世界模型是Watts和 Strogatz在1998年提出了一个兼具小世界性和高聚集性的网络模型（简称WS模型）。小世界网络模型以规则网络模型为基础，通过将规则网络模型中的每条边以概率p随机连接到网络中的一个新顶点上，构造出一种介于规则网络和随机网络之间的网络。因此，规则网络模型和随机网络模型实际上可以看作是小世界网络模型在p=0和p=1时的特殊情况。

图 1 小世界网络模型（中）、规则网络（左）和随机网络（右） Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J]. nature, 1998, 393(6684): 440-442.
小世界网络的顶点度分布为指数分布形式，而大多数的真实网络的度分布经研究发现更接近幂律分布，因此并不能完全用以描述真实世界中的网络。

无标度网络

无标度网络也称无尺度网络，其特征是在网络中的大部分顶点只和很少顶点连接，而有极少的顶点与非常多的顶点连接。现实中的许多网络都有无尺度网络的特征，如因特网以少量的节点来实现大量终端之间的元数据交换，金融系统网络利用少数服务站点实现大范围的金融时间控制、社会人际网络中、常常存在着少数人脉特别广的人等等。
有关无标度网络最著名的模型就是Barabási与Albert提出的BA模型，这个模型通过两个假设来解释现实世界复杂网络的无尺度特性：
增长性：现实世界中的网络大多都是不断增长而来的，比如因特网中常常会有新的终端以及服务器加入、金融系统中常常会有新的金融站点加入、人际交往中常常会有新朋友等等，这意味着网络中的节点会不断地加入。
择优连接模式：新的顶点在加入网络时，会倾向于与有着更多连接的端点连接，例如因特网中直接与服务器端点连接会有更高的网速、金融系统中与金融服务节点相连会有更好的安全性和时效性、人际交往中人们通常喜欢和人脉广的人交朋友等等，这意味着顶点会优先选择度数大的顶点连接。
Barabbas与Albert两人基于以上两个假设利用多种方法进行了模拟分析，经过充分长时间的演化后，BA网络的度分布逐渐平稳在指数为3的幂律分布。这是复杂网络研究中的重要一步。后来还有学者对此进行推广，演化出了适应度模型、居于世界演化模型、复制模型、分层模型等。

自相似网络

自相似是相似中的一种特殊情况，它是指系统的部分和整体之间具有某种相似性，这种相似性不是两个无关事物间的偶然近似，而是在系统中必然出现并始终保持的。这种自相似是层次复杂网络共有的拓扑性质，而自相似又是分型的一个基本特征，所以复杂系统与各层次子系统之间的自相似性，可以利用分形加以描述。

权重演化网络

现实网络中的关系大多是有权重的，如因特网中服务器节点之间的网络线路更好，各个终端购买的互联网套餐费用也会导致网络连通速率不同、金融系统中各个金融服务节点之间的连通性级别是最高的、人际交往中人与人之间的关系有好坏之分，网络顶点之间的连接强度大多是有区别的，因此传统将所有顶点之间的权重均视为相同的模型不能充分表征这一点。因此，有学者提出了一种权重演化模型: 假定节点权重正比于节点的度数 ，也即度数大的节点拥有更大的权数。结果表明，其度分布也符合幂律特征。

复杂网络研究应用

网络传播动力学研究

传染病在人群中的传播、社会中谣言的扩散、金融系统中风险的传播、因特网中计算机病毒的传播，这些都是发生在复杂网络上的系统动态性传播行为，一般把这种行为或者性质称为网络传播动力学研究。研究发现，复杂网络上的传播动力学行为相较规则网络和随机网络都有着非常大的区别。
经典的SIS、SIR两种模型是疾病传播模型，他们将真实系统的网络假定为规则网络或者充分混合均匀网络，前者的顶点状态处于健康易受感染和已感染有传播性两种状态；后者增加了一个既不会感染也不会传播的免疫状态，相当于从网络中剔除这个顶点。但如前文所述，规则网络并不能很好的表示真实世界中的网络，因此有学者研究了小世界网络、无标度网络中的疾病传播动力学行为。结论显示，小世界网络与无标度网络中的传染病传播阈值都小于规则网络，且无标度网络的传播阈值非常接近零，也就是说病毒的传染强度很小也能造成很大的传播；在相同的传染强度下，疾病在小世界网络或无标度网络中传播的传染范围明显大于其在网络中的传染范围，也就是说真实网络比规则网络更易传播。
这是指网络传播动力学在疾病传播方面的研究，还有学者将网络传播动力学研究扩展到多个领域。如复杂网络上的交通传播动力学特征和传播规律的研究为消除交通拥堵提供了有效的控制策略以及合理的交通规划方案；将网络传播动力学应用到社会网络中的谣言传播中，有助于优化社会谣言防控；还有学者在知识、在线社交网络、灾害等诸多邻域利用复杂网络中的传播动力学进行研究。

社区挖掘

社区，是指具有相似连接结构的节点集合，社区内部的顶点间关系紧密，社区内部与外部顶点间关系稀疏[[[] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.]]，这与聚类算法中簇的定义类似。实际上，社区挖掘目的与聚类相同，只不过社区挖掘处理的对象是网络，社区挖掘没有社区数量的限制，各个社区之间也可以重叠或者嵌套。

图 2 网络的社区结构 赵卫绩, 张凤斌, 刘井莲. 复杂网络社区发现研究进展[J]. 计算机科学, 2020, 47(2): 10-20.

根据网络是否动态变化，可将网络社区发现分为静态社区发现和动态社区发现。静态社区挖掘方法可以进一步分为非重叠社区挖掘算法与重叠社区挖掘算法。如基于模块度优化、标号传播、信息论或谱分析的非重叠社区挖掘方法；重叠社区挖掘算法包括基于团渗透改进的算法、基于模糊聚类，基于非负矩阵分解、基于种子扩展、基于混合概率模型、基于边聚类的社区挖掘算法。静态社区发现可以探测人际关系网络的社团，但是在真实的世界中，网络中的顶点通常是动态更新的，不断会有顶点加入和退出，动态社区发现的主要工作是识别出动态复杂网络中不同时间段的社区结构[[[] 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究新进展[D]. , 2011.]]。

关键节点挖掘

小世界效应与无标度特性使得复杂网络中的节点分布呈现不均匀的现象， 少数节点具有大量连接，处于重要地位， 例如在国际贸易中对整个贸易体系有重要影响的一些国家，相比于大多数普通节点，这些少数节点对于整体网络有着更大的影响，再如因特网以来少量的节点来实现大量终端之间的元数据交换，金融系统网络利用少数服务站点实现大范围的金融时间控制、社会人际网络中、常常存在着少数人脉特别广的人。因此准确识别复杂网络中的重要节点，对于优化复杂网络的结构与功能具有重要意义。

演化博弈动力学

博弈论是研究个体与个体之间的合作或者竞争关系的一门学科，主要研究个体在相互作用过程中如何获得最大利益的理论，是对合作与竞争关系的一种反映。演化博弈论以种群为对象，认为个体的策略可能会发生变异，这与实际网络的特征较为吻合，因此关于复杂网络上的演化博弈动力学的研究得到了越来越多学者的参与。演化博弈动力学主要通过将囚徒困境、雪堆模型等经典博弈模型演化到网络空间中进行分析，这种方式能将网络中的距离、连接关系等量化为指标，能够对复杂网络中的因果涌现、预测等方面提供支撑。

结束语

复杂网络已经成为目前研究真实世界网络的一个范式，其在多个领域都有着出色的成绩，但是目前复杂网络本质上还只局限于描述成对的交互关系，现实世界中的系统通常由三个及三个以上的单元构成高阶交互关系。超图在社会科学、生物科学、信息科学等邻域都有了广泛的应用。超图中超边的引入不仅可以描述多元间的关系，还能降低网络结构的复杂度，很好地刻画了网络中的复杂关系。将超图相关理论引入复杂网络中或许会有助于复杂网络相关研究。

引用

Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977: 35-41.
Albert R. Attack and error tolerance in complex networks[J]. Nature, 2000, 406: 387-482.
“小世界网络 - 维基百科，自由的百科全书,” Zh,https://zh.wikipedia.org/ wiki / %E5%B0%8F%E4%B8%96%E7%95%8C%E7%B6%B2%E8%B7%AF(访问时间 Jan. 1, 1970).
Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J]. nature, 1998, 393(6684): 440-442.
Barabási A L, Albert R. Emergence of scaling in random networks[J]. science, 1999, 286(5439): 509-512.
刘涛, 陈忠, 陈晓荣. 复杂网络理论及其应用研究概述[J]. 系统工程, 2005, 23(6): 1-7.
Yook S H, Jeong H, Barabási A L, et al. Weighted evolving networks[J]. Physical review letters, 2001, 86(25): 5835.
周涛, 傅忠谦, 牛永伟, 等. 复杂网络上传播动力学研究综述[J]. 自然科学进展, 2005, 15(005): 513-518.
Moore C, Newman M E J. Epidemics and percolation in small-world networks[J]. Physical Review E, 2000, 61(5): 5678.
Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks[J]. Physical review letters, 2001, 86(14): 3200.
李树彬,吴建军,高自友,林勇,傅白白.基于复杂网络的交通拥堵与传播动力学分析[J].物理学报,2011,60(05):146-154.
朱志. 基于复杂网络传播动力学的谣言传播研究[J]. 东南传播, 2009 (12): 19-21.
王辉, 韩江洪, 邓林, 等. 基于移动社交网络的谣言传播动力学研究[J]. 物理学报, 2013, 62(11): 110505.
褚建勋. 基于复杂网络的知识传播动力学研究[D]. 安徽: 中国科学技术大学, 2006.
雷宏振, 贾悦婷. 基于复杂网络的在线社交网络特征与传播动力学分析[J]. 统计与决策, 2015 (2): 114-117.
翁文国, 倪顺江, 申世飞, 等. 复杂网络上灾害蔓延动力学研究[D]. , 2007.
Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.
赵卫绩, 张凤斌, 刘井莲. 复杂网络社区发现研究进展[J]. 计算机科学, 2020, 47(2): 10-20.
骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究新进展[D]. , 2011.
湛文涛,纪庆群.复杂网络上演化博弈动力学研究综述[J].计算机光盘软件与应用,2012,15(22):75-76.
索琪,郭进利.基于超图的超网络:结构及演化机制[J].系统工程理论与实践,2017,37(03): 720- 734.