复杂网络的基本概念、模型及应用

复杂网络的基本概念、模型及应用

一、复杂网络的基本概念

前面我们在《多主体建模和智能优化算法》一文中,介绍过实际网络,有了这些实际网络，我们就要对它进行研究。在研究之前，我们必须把它抽象成可以用数学进行描述的问题，即复杂网络。

1.复杂网络的数学描述

网络G=（V,E），由点集V（G）和边集E（G）组成的一个图，可分为无向、有向和加权网络。

令ei∈E（G），每条边ei有V（G）中的一对点(u,v)与之对应；如果任意(u,v)与(v,u)对应同一条边，则称为无向网络，否则为有向网络；如果任意∣ei∣=1，则称为无权网络，否则为加权网络。

2.无向网络

无向网络是最简单的网络类型，它节点跟节点之间的连边只表示连接关系，无方向的概念，如图1所示。

图1无向网络的邻接矩阵

无向网络由节点和连边构成，我们把节点和连边用矩阵进行刻画。图1展示了一个非常小的网络，把它写成矩阵的形式，实际上是一个4×4的矩阵，由于节点1和节点4之间有连边，我们把矩阵中（1,4）这个地方记为1；节点2和节点4有连接，那么第二行第四列我们记为1；节点3和节点4是有连接，那么第三行第四列记为1；节点4和节点1、2、3都有连接，所以第四行的第1、2、3列都记为1，其他地方是0。这个矩阵就把一个网络的信息全部记录下来了，通过数学语言对网络进行了抽象。对于无向网络，实际上我们可以对应的把它做一些调整，就可以模拟很多现实中的网络。

3.有向网络

有向网络是另外一类复杂网络。例如微博，在微博网络中，每一个节点是一个微博用户，节点跟节点之间的连边表示“关注”关系，由于我粉你，但你不一定粉我，所以连接关系是有向的。同样的，还有引文网络，在引文网络里每一个点是一篇文章，文章跟文章之间的引用关系是有向的，我引用你，你不一定引用我，所以这是有向网络。对于有向网络，我们把它抽象成矩阵的形式进行描述。但是，有向网络与无向网络在矩阵层面上的最大区别在于无向网络的矩阵一定是对称的，有向网络的矩阵不一定是对称的。

4.加权网络

加权网络是更复杂的网络。我们在实际网络（社交网络）中提到科学家跟科学家之间的合作可以抽象成复杂网络，但其中的连边可以表示科学家跟科学家的合作次数。在矩阵中，每一行每一列的元素表示合作次数，即数值不一定仅记为1和0，数值大小代表权重。因此，不同类型的复杂网络都可以通过数学语言抽象的矩阵来进行刻画。

5.二分网络

后面我们在介绍关于信息挖掘部分会涉及到一个与之前介绍过的不同的网络，二分网络。如图2所示，二分网络是由两类的节点来构成的，它可以刻画很多在线系统。在线系统里面，一类节点表示“用户”，另外一类节点表示“商品”，或者是电影、视频等等。在二分网络中，连边存在于两类的节点之间，同类节点之间没有连边。它可以帮助刻画在线用户的行为，例如购物，你在淘宝上买了一个东西，那么你就作为一个“用户”节点，你购买的东西是“商品”节点，然后把这两个节点之间连一条边。二分网络能抽象用户的在线行为，对应的邻接矩阵与前文介绍的网络的邻接矩阵有所不同，它不再是一个方阵。前文介绍的网络的邻接矩阵一定是方阵，因为横轴纵轴对应同一类节点，而二分网络对应的邻接矩阵，它是n×m，n是“用户”节点，m是“产品”节点。如果n和m不相等，这就不是一个方阵。如果1号用户购买了5号产品，就在（1，5）处记为1；如果没有购买这个产品，就在相应处记为0。

图2二分网络

6.多层网络

还有一类最近研究比较多的网络，多层网络。多层网络是更复杂的系统。例如航空系统就可以抽象成多层网络。我们知道很多国家都有自己的航空公司，每家航空公司都有自己的航线。一家航空公司就可以形成一个自己公司内部的航空网络。我们把若干家航空公司的内部网络重叠（不一定是叠加），就可以用多层网络来构建一个航空系统。理论上，多层网络有多种刻画方式，例如用大矩阵刻画，把节点抽象成大矩阵里面的行列，也可以抽象成很多小矩阵，例如图3中有5个小矩阵，但因为有时层与层之间会有连接，所以需要更多的矩阵去刻画一个多层网络。

图3多层网络

7.度与度分布

复杂网络中有一个经典的概念——度，用于衡量节点的连边数，即一个节点有多少条连边，我们就定义它的度是多少。例如一个节点有3条连边，它的度就是3。

网络中，节点在不同度值上的分布称为度分布。我们通常用度分布的频数统计图展现网络中节点的连边数的分布情况。

二、复杂网络基本模型

我们从最原始的研究开始介绍复杂网络的基本模型。复杂网络起源于1998年和1999年在《Nature》和《Science》杂志中的两篇文章，分别提出了小世界网络模型和无标度网络模型，推动了复杂网络领域近20年的发展。

1.规则网络与随机网络

最早在物理学领域的研究中应用较多的网络模型是规则网络，例如晶格网络。与规则网络相对的是随机网络，在图论中关于随机网络的研究比较多，任意两个节点之间以一定概率随机连接，就会形成随机网络。

这两类网络在很多传统科学研究中较为常见，但是当现实的数据收集越来越多时，人们发现这两类传统的网络模型对现实中网络的刻画能力越来越差，直到上世纪90年代末小世界网络和无标度网络模型的提出。

2.小世界网络及六度分离

小世界网络模型描述的对象是社交网络。社交网络有两个特点是传统模型无法刻画的，一是有比较大的集聚系数，二是最短路径非常小。

集聚系数指一个节点直接相连的其他节点（下文称为“邻居”）之间的连边数。如果“邻居”之间连接非常紧密，那么这个节点的集聚系数就比较大。在社交网络中这一现象非常普遍，例如一个人的朋友之间相互认识的可能性是很大的，他们之间很可能也是朋友。

另外，在复杂性科学中有一个概念叫六度分离理论。六度分离理论指在这个世界上，看似没有关系的任意两个人都可以通过六步左右的路径连接在一起。例如一个股票专家做过一个实验，将一封有关股票信息的电子邮件发送给一个陌生人，并要求他把电子邮件转发给一个爱炒股的人,当这封电子邮件第六次转发时，竟然又转发到股票专家手中。经过无数次实验结果相同,所以得出初步结论：任何两个陌生人之间，可以通过六个人来建立联系。我们可以通过有限的步骤把由70多亿人组成的社交网络中任意两个点通过非常短的步骤连接在一起，这就是非常小的最短路径特点。

但是这两个特点在规则网络和随机网络里都不能被体现。例如，规则网络的集聚性特别高，但是最短路径可能很大；而随机网络因为连边随机，所以随机选取两个点，它们能以非常短的距离连接，但它的集聚性不高，我们任意选取一个点会发现它的邻居之间往往连边很少。所以，规则网络和随机网络仅仅分别刻画了社交网络两个特点之一。

1998年发表在《Nature》期刊的一篇文章通过非常简单的模型把社交网络的两个特点呈现出来了，即这一模型既有规则网络的高集聚性，又有随机网络小的最短路径特点。在规则网络的基础上，引入一个非常小的概率

，对原有的一条连边以概率

剪断，然后随机在网络里选取两个节点连接在一起。当

时，任意一条连边都不会重新连接，即规则网络；如果

，每一条连边都会以100%的概率被剪断，然后重新连接到网络里的任意两个点，这样的一个极端情况就是随机网络；当

时，网络不但能保证原网络比较高的集聚性，而且因为剪断了少量的连边使之重连，所以能出现一些长连边，从而有效地缩短了整个网络的最短路径。由此看出，小世界网络提出了一种能够更好重现社交网络的模型。

图4规则网络、小世界网络、随机网络

3.无标度网络及网络增长

1999年《Science》期刊上发表的另外一篇文章认为，虽然小世界网络模型能够很好地重现社交网络，但是社交网络另一个非常重要的特点被小世界网络忽略了。众所周知，实际网络是随时间不断增长的，例如引文网络和微博网络，因为有新的文章被发表，有新的用户使用微博；社交网络也是随时间不断增长的，但是小世界网络它的节点数是固定的。为了重现这一特点，文章提出了一个增长网络的模型，首先有若干个初始节点，然后每一步都会有新的节点加入，而这个新的节点会与一些老的节点相连，演化结束以后，会得到一个网络，我们称之为无标度网络。这个网络有一个性质是小世界网络无法重现的，即实际网络中广泛地观测到的度不均匀的现象。例如在微博网络里，少数的大V有很多的粉丝，而大多数普通用户就可能只有二三十个粉丝，这种不均匀性是小世界网络无法刻画的。再例如引文网络中，一些文章的被引用次数是非常多的，成千上万，但是绝大多数文章的被引用次数都非常少，而这样一个增长网络刻画的就是这一现象。因为每一个节点进入的时候只能连比它更老的节点，这使得老的节点会有更长的时间去积累连边，所以在这个网络里，大量新的节点的连边数都比较少，若干个老的节点的连边数会非常多。这个网络模型解释了实际网络里的“二八”效应，20%的点占了80%的连边数。

这两篇文章让人们发现，实际网络有很多特点是传统的网络模型无法刻画的。除小世界网络和无标度网络模型之外，还有哪些实际网络的特性未被发现，所以近年来涌现了一大批的对于实际网络进行建模的文章，提出的模型也是千差万别。

小世界网络和无标度网络度分布如图5和图6所示（p是连接概率）。我们发现，小世界网络的度分布接近于正态分布，而且横轴基本上是同一数量级的（10的1次方）。小世界网络节点的度值差别不大。而无标度网络的度分布频数统计图中（横轴是节点的度，纵轴是该度值的节点数在网络里面所有节点所占的比例），有很大比例的点的度非常小（10的1次方，10的0次方），有少量的点的连边数极其多，数量能达到10的2次方，10的3次方，所以无标度网络展现了节点度分布极度不均匀的特点，其中大量的点是小度节点，有少量的节点的连边数特别多，而这种分布被称为幂律分布（在频数统计图上坐标轴取双对数，图像是一条直线）。

图5小世界网络的度分布

图6无标度网络的度分布

三、复杂网络在解决实际问题中的应用

1.网络的鲁棒性

当出现扰动时，我们需要评价网络的受损程度，如果网络的受损程度小，系统还能正常运行，我们就称这个网络具有鲁棒性。网络的鲁棒性涉及到渗流理论，关注的是网络中的最大连通集团。很多实际网络并不是全连通的，但会有一个最大的连通集团，其他节点散布在最大连通集团周围。最大连通集团非常重要，肩负着网络里面的很多功能，例如在航空网络里，如果一个点不在最大连通集团之内，这个点的航班无法到达很多其他的空港；在神经网络里，连通的神经元之间才能传递信息；在电力网络里，网络须有较好的连通性才能给一个点供电。因此，为确保网络的鲁棒性，应该保护网络中的最大连通集团。

实际网络的特点是有大量的节点连边数特别少，但是有少量的节点连边数特别多。我们以航空网络为例，航空网络受到外界的干扰，如果是自然灾害影响，因为自然灾害一般没有目的性，大多是天气导致的，它可能会影响到某一些空港，使得空港的飞机无法起飞。在这种随机影响下，整个网络的功能性到底能有多大的保持？那么发现在这样的网络里面，我们将受到灾害影响的节点从航空网络里去掉，因为绝大多数的节点度值都很小而整个网络的最大连通集团还比较大，所以航空网络对于这种随机干扰，它的鲁棒性很高，对灾害的敏感性不那么强；但是如果是外界蓄意攻击，例如一个恐怖组织计划破坏航空系统，必然不是随机选取一个空港进行攻击，而是攻击网络的中枢——最繁忙的机场。我们把这个机场从网络中删掉，最后发现网络的最大连通集团变得特别小，使很多空港的飞机都无法与其他空港连接。大量的实际网络都是由这样的结构所刻画的，而这样的结构的鲁棒性和脆弱性是共存的。因为网络中有大量的点都是小度值的，所以随机扰动并不能影响这个系统的运转，但是对于蓄意攻击，网络是非常敏感的。

2.网络拥堵

交通拥堵是大城市病之一。我们对交通进行建模，评价交通的运行状况，评价交通网络的设计是否合理，会不会造成大范围的拥堵。例如将北京的道路抽象成网络的形式，每一个节点表示一个路口，每一条边表示路口与路口之间的道路。复杂网络中有一个衡量节点重要性的指标叫做介数，表示通过一个点连接网络中任意两点最短路径的数量，如果通过的最短路径数量很多，那么这个点的介数就大。我们把道路系统抽象成网络后，就可以计算网络中每一个点的介数。那么我们可以列出介数很大的若干个点，它们担负着若干个集团之间相互沟通的任务。如果一个网络中的节点介数分布非常均匀，那么整个系统的交通流就被平均分担到了各个路口，一般不会出现大量的拥堵。但是如果有若干个点的介数特别高，就说明这个路网的设计不太稳健，一般会造成这个点上的拥堵。如果需要评价一个网络可能出现的拥堵情况，我们就可以观察节点中最大的介数，如果最大的介数都比较小，网络的交通流分布就不会特别集中在若干个节点上，发生拥堵的可能性就小。

我们以一个实例来说明上述的方法。如图7所示，我们把北京西站附近的路网抽象为复杂网络，每一个路口抽象为一个点，路口与路口之间的道路抽象为一条连边。摄像头可以记录道路上的交通情况。图中道路的颜色不是表示车的数量，而是表示车流的速度。电子地图中的实时路况信息，颜色为红色并不表示车多，而是表示道路上车速比较慢。在网络建模并获得了实际数据之后，我们就观察每条道路的车流速度，车流速度慢就标为红色，车流速度快就标为绿色。当然在不同的时间情况会不同，9点的时候红色的道路就特别多，12点的时候红色的道路就特别少。我们把网络里红的连边删掉，然后观察网络的连通集团到底会发生什么变化。当然，删去的连边越多，网络的连通性就越差。

图7北京西站附近的交通图

图8最大连通集团的变化

为什么我们要关注网络的连通性？因为在交通网络里，如果删去若干条连边后，一个点和别的点无法连在一起，在现实中你就永远到不了上班的地方。把这些特别拥堵的连边从网络里删掉，因为这些道路拥堵了，你无法通过，就堵在路上了。如图8，我们发现网络中的最大连通集团含有节点数随逐渐删去连边而下降，但不是平缓下降，而是在某一点陡降。这说明在网络里，拥堵的连边往往沟通了两个区域，它并不是在网络里随机分布的，而是往往出现在网络里介数比较大的点上。所以当删到某一条边后，你两个区域不再连通，那么网络中的最大连通集团就陡降了。交通网络里会存在若干这种瓶颈路，一旦把它们删掉，网络的沟通情况就会变得特别差，从而分成两个集团，而如果要疏导交通或提高交通的运行体验，不需要全面地提升整个网络，例如不需要把北京市所有的道路拓宽两个车道，只需要把若干瓶颈路拓宽，就会很大程度上缓解交通拥堵。

3.网络传播

网络传播问题的研究对象是社交网络。2013年发表在《Science》上的一篇文章研究了网络上的传播过程所具有的特点。它收集了2003年和2009年的两组全球的数据，2003年是非典疫情爆发的一年，2009年是H1N1流感爆发的那年。数据中每个国家具有两个数据，第一个数据是国家离病毒源头的距离，我们知道SARS疫情是在中国爆发的，H1N1是在墨西哥爆发的，第二个数据是这个国家在中国爆发疫情后多长时间被感染。收集完数据以后，作者就做了散点图，每个点代表一个国家，横轴是它离中国的距离，纵轴是它感染病毒的时间。结果发现一个国家在什么时候被感染病毒与它距离源头有多远没有明显的关系。你离中国特别近，也不一定你明天就感染病毒，你离中国特别远，也并不意味着你很安全，距离的远近，实际上对病毒的传染并没有作出一个很好的解释。

图9疾病传播时间与和疾病起源地有效距离的关系

作者还关注到了全球航空网络，搜集了两个空港之间每天的航班数量及人流量，从而定义了一个有效距离

其中m和n分别代表一个国家，

表示这两国之间的日常人流量，

越大，

越小，即如果两个国家之间人流量特别多，这两个国家的有效距离就越小。在重新定义距离后，作者作出了新的散点图，纵轴依然是这个国家感染病毒的时间，横轴表示有效距离，结果发现散点大多落在了一条直线上。这说明你离一个国家的有效距离比较近，你就会在比较早的时间感染这个病毒；如果一个国家离另外一个国家有效距离比较远的话，那么你感染这个病毒的时间也会比较靠后，病毒要经过比较长的时间才能传播到这个地方。所以决定一个国家感染病毒的快慢，实际上是网络的有效距离，而不是地理距离。

我们在日常生活中也有同样的感