复杂网络理论基础：网络的基本概念与特征度量方法

（一）复杂网络的基本概念

1.网络

网络（network）是一类描述自然和人工系统的模型，是一种组织形式的表现。一个网络是具有一定特征和功能的群体。网络分析并不只是一个简单的理论任务，它需要收集数据来对现实的网络进行制图。虽然网络可以用图片语言进行描述，但网络不仅仅是图，它还承载一定的功能和状态，运用所制成的网络图，可以用来分析网络的拓扑性质。

复杂网络具有海量的节点数和复杂的连线拓扑结构。随着大型数据库和计算机能力的提升，这样的实证研究也开始出现在各个领域。在复杂网络中，节点是系统中的元素，边则代表节点间的相互作用，例如因特网（Internet）可以看作是由不同路由器作为节点，根据不同协议，相互间物理或逻辑连接作为边的复杂网络；巨型的基因网络则可以看作是由每个蛋白质作为节点，而蛋白质之间的化学相互作用为边；在食物网中，节点是各种具有营养的生物物种，相互的猎食关系则作为它的边；在新陈代谢网络中，节点是各式各样的酶，边则是代谢关系；在社会网络中，独立自主行为者为节点，边则代表了独立自主行为者之间的关系。由于庞大的规模以及相互之间的复杂性，许多网络的拓扑性质仍然是未知或者在探索中。

2.小世界网络

1967年，美国社会心理学家特拉弗（Traver）和米尔格兰（Milgram）提出了一个著名的理论：六度区隔，“在这个世界上任何人之间都可以与彼此建立起关系，大约只需要通过六步”。这也是最早被强调的小世界效应理论之一。小世界效应的内涵在于无论怎样巨大的网络，都可以有任意两个节点存在很小的路径长度使得二者相连。这一现象揭示了在我们客观世界中，许多复杂网络存在最为便捷和有效的传递方式。

小世界理论（WS网络）最早是由沃茨（Watts）和斯托加兹（Strogatz）提出的。它是一种新的办法，用于构建一种介于固定网络与随机网络之间的网络。在一个网络中，两个节点之间的连接概率可以设为P。在一个固定网络中，节点必然与它邻近的节点相连，所以P为0。固定网络还具有高节点集聚系数和较大的节点间分离程度的特征。随机网络中，情况则发生了变化，两个节点的连接概率P变为整数1，开始拥有低集聚系数和较小的节点间分离程度。

3.无标度网络

无标度网络的主要特征就是少部分节点承担着连接大多数节点的作用，同时这些少数节点有较大的抗压能力。无标度网络被认为可能是小世界网络模型下的一种，但是两者之间有存在着许多差异。

小世界网络模型最早由巴拉巴西（Barabasi）和艾伯特（Albert）提出。他们发现网络中节点的度分布相对均匀，而在现实中多数网络的度分布是不均匀的，且往往满足幂律分布。

在一个航空网络中，如果存在机场数为k0，在这个基础上，每增加一个新的机场，那么新机场就会随机生成k条航线。假设该原始网络机场i的连接度为ki，则机场i与新机场的连接概率如式（4-1）所示。

无标度网络特性在于其扩张性，表明它可以无标度地不断扩张，同时它的局限在于只考虑新节点和原本网络存在的节点连线，与真实网络仍有一定差距。

（二）复杂网络特征度量方法

网络统计性质又被称为网络的静态几何量。网络可以用式（4-2）表示：

其中X就是网络中所存在的节点，也可以理解为网络中点的集合。Y则表示节点与节点连接成的边，可以理解为网络中点与点连线的集合。x=| X |是网络节点的数量，y=| Y |是网络边的数量，显然我们可以得到y≤x（x-1）。M=（mij）是用于研究网络的邻接矩阵，i和j是网络G中任意的节点。在矩阵M中，如果节点i和节点j是相互连接的，且i ≠ j，那么mij=1。反之，mij=0。(https://www.xing528.com)

1.平均路径长度和节点可达性

平均路径长度（Average Path Length）表现的是整个网络的分离程度。它在航空网络中主要拿来测量各个机场之间的最小衔接长度，即转机次数，用于把握航空网络的整体性质和度量各个机场的紧靠程度或分离程度。同时，平均路径长度还可以检测航空网络的传输性能和传输效率。

平均路径长度定义如下：对于节点i和节点j（i，j∈X），且i ≠ j，它们之间的最短距离为dij。那么整个网络的平均路径长度计算公式如式（4-3）所示。

网络节点可达性可以用于判断网络节点的区位条件的优劣，是节点i到其他所有节点距离平均值的倒数，数值越大，可达性越高，如式（4-4）所示。

2.聚类系数

聚类系数（Clustering Coeき cient）也可以认为是网络集聚系数。它是网络中节点趋于聚集在一起的量度，即节点的聚集程度。而平均聚类系数（Average Clustering Coeき cient）则反映了整个网络的聚集化程度。网络平均聚集程度主要是为了考察网络节点各自近邻之间有多少共同近邻。一个节点的聚类系数是指它近邻相连接成边的数目占最大可能连接数目的比值。定义如下：对于任意节点i，与该节点相连接的节点集合为Ki，则该节点i的近邻数量为ki=| Ki |，而Ki个近邻节点之间实际存在的边数为Ei和总的可能存在边数为C2 ki，那么节点i的聚集系数可以被定义为：

所有节点的平均聚类系数的计算公式则为：

3.度与度分布

度值（Degree）是网络拓扑中最稳健的度量概念之一。网络G是由节点集合X和连接它们的边集合Y构成，那么所有与节点i连接的边的数量Di就是节点i的度（degree）。度是一个节点在网络G中的关系总量：从该点出发和接收回来的关系总数。在有向网络中，可以有点入度和点出度。但本文观察航空网络的无向关系。

由节点的度可以得到最小度和平均度两个延伸概念。最小度就是网络中度最小的节点的度，如果在网络G中，最小度大于等于1，于是网络G可以说在整体连接上是连通的。在无向网络中，各个节点的度的平均值为网络的平均度：

网络G中的度分布P（k）表示网络G的任意节点i恰好有k条边的概率分布。在大部分现实网络中，度分布一般以幂律分布的形式出现，当然也可能是高斯分布或者指数分布。

（四）介数

介数（Betweenness Centrality）是一种有全局特性的变量，具有很强的现实意义。它分为节点介数和边介数两种。定义如下：在航空网络中，Wuk为（u，k）的最短航线集合，另wuk=| Wuk |，wuk则表示为从u至k的最短航线条数。wuk（i）则是从u至k必须经过机场i的最短航线条数，直观上来说介数就是表现机场i作为桥梁的重要性。节点介数公式如式（4-8）所示。

B（i）表示节点i的介数。类似地，可以定义边的介数。介数的现实意义可以表现为：在航空网络研究中，介数的分布特征可以具体反映不同航空机场在整个航空网络关系中的连接地位，同时确保航线安全都具有十分重要的影响。