2.3 网络中的统计特性

真实世界中存在的大量复杂系统都可以通过网络加以描述，如神经网络、计算机网络、电力网络、社交网络、交通网络等。对网络最早进行研究的数学家在考虑网络时，往往只关心节点之间有无边，而不在意节点具体在什么位置、具体是什么状态等。这种不依赖节点位置和形态就能表现出来的性质称为拓扑性质。早期的科学家们认为真实系统可以用一些规则结构表示，如二维平面上的欧几里得格网，它看起来像格子 T 恤衫上的花纹，又如最近邻环网，它总是会让你想到一群手牵手、围着篝火跳舞的姑娘。经典图论倾向于用规则的拓扑结构模拟规则网络；20世纪中叶，Erdos和Rényi想出了构造网络的新方法，认为两个节点之间的连边是由一个概率决定的，并依据这样的方法建立了随机网络模型，该模型在接下来的 40 多年里成为科学家研究真实网络的有力工具。近十几年来，大量研究发现，现实中不同种类的复杂系统表现出了很多共同的宏观性质，而这些性质是简单的规则网络和随机网络所不具备的，因其节点众多，故称其为复杂网络，如图2.16所示。

用网络的观点描述客观世界起源于 1736 年德国数学家欧拉解决哥尼斯堡七桥问题。复杂网络研究的不同之处是，首先从统计的角度考察大规模节点及其连接之间的性质，这些性质的不同意味着不同的网络内部结构，对这些统计特性的描述理解是研究复杂网络的关键。

本节首先主要讨论网络中常用的几种统计特性，包括度分布、平均路径长度、聚类系数，以及其他一些不常用的统计特性，如网络弹性、介数等；然后引入4种网络模型来解释常用的统计特性，介绍不同类型网络的统计特性的差异。

2.3.1 统计特性

本节主要介绍网络中的三种统计特性：度分布、平均路径长度和聚类系数。其中，度分布是描述节点特征最简单的概念，也是研究得最多的概念，指节点的度在网络中如何分布；平均路径长度是所有节点对之间距离的平均值，它描述网络中节点间的分离程度，即网络有多小；聚类系数衡量网络节点聚类的情况。下面具体讨论这三种统计特性的定义。

1.度分布

一个具体网络可抽象为由一个节点集V 和一个边集E组成的图G=（V，E），节点数记为N=，边数记为M=。

度是网络中一个点与其他点的连接数量，度分布是整个网络中各个点的度数量的概率分布。对于有向图，有入度和出度之分，入度是指向该节点的边的数量，出度是指从该节点出发指向其他节点的边的数量。网络中节点的度分布用分布函数p_k表示，其含义为一个任意选择的节点恰好有k条边的概率，也等于网络中度数为k的节点数占网络节点总数的比值。图 2.17 中显示了无向图的度分布。

对于一些事物，个体与个体之间的差异不大，比如人的身高，中国成年男子的身高绝大多数为 1.70 米。正态分布描述类似这样的群体特性大致相同的情况。对于另一些事物，人们发现现实社会同很多网络的度分布服从一定的规律，如下所示。

·在社交网络中，少部分人有大量的朋友，大部分人只有少量的朋友。

·很多网站每月的访问量不到 1000 次，少量网站每天的访问量超过 100万次。

·一个国家的财富状态，低收入和中等收入阶层占绝大多数，高收入阶层只占极少数，极少数的富人赚走了绝大多数的钱。

这样的个体与个体之间的差异明显，幂律分布描述类似这样的多数个体量级很小、少数个体量级很大的情况。幂律分布和正态分布展示了两个非常不同的世界。以收入为例，在正态分布中，中等收入阶层占绝大多数，低收入和高收入阶层占极少数，这种分布被认为是非常理想的社会，但真实世界的趋势越来越像幂律分布。

幂律分布广泛存在于现实世界的众多领域，如生物学、物理学、社会学、经济学等，它同样存在于真实世界中的各种复杂网络，如社交网络，互联网等。这些网络的节点都呈现了这样一种现象：大多数“普通”节点拥有很少的连接，而少数“热门”节点拥有极多的连接，这些“热门”节点称为枢纽节点，即节点度呈幂律分布的直观表现是：大多数节点的度较小，而少数枢纽节点的度很大。以收入或人口数为横坐标，以不低于该收入值或人口数的个体数或概率为纵坐标，可以绘出一条向右偏斜得很厉害累积分布曲线，这条曲线从最高的峰值开始极速下降，并拖着长长“尾巴”。这种“长尾”分布表明，绝大多数个体的尺度很小，只有少数个体的尺度相当大。图 2.18 中显示了长尾分布示意图，实际上长尾分布就是幂律分布。

在统计学中，幂律是两个量之间的一种函数关系，其中一个量的变化会导致另一个量的相应幂次的比例变化，幂律分布的一个属性是它们的标度不变性。给定一个函数关系 f （x）=ax-k， a表示节点的度，对参数x作常量c的标度变换，会导致幂函数作本身幂指数比例的标度缩放，公式表达为

式中，∝表示成正比，取 f （x）和x的对数，可得

上式表明，幂律分布的双对数坐标图是一条直线，这通常被视为幂律分布的标志。对于实际数据，这种线性是幂律关系数据的必要条件而非充分条件。图2.19中显示了幂律分布及其双对数坐标图。

符合幂律分布的网络称为无标度网络（Scale-free Network）。现实生活中大部分社交网络是无标度的，如在演员合作网络中，演员是节点（群众演员不算），两人出演过一部影片，就表明有一次合作。经常出演的明星有机会和很多不同的人合作，如成龙、周星驰等，他们的度大，普通群众的度小，因而演员合作网络节点的度具有幂律分布的特征，也就是无标度网络。

2.平均路径长度

在网络研究中，定义最短路径（Shortest Path）为网络中任意两个节点之间多条路径中长度最小的路径。网络中任意两个节点之间最短路径的最大值称为网络直径，也就是说，要求一张图的直径，首先要求任意两点间的最短路径，在所有的这些最短路径中，最长的是这张图的直径。在由N个节点组成的网络中，第i个节点到第 j个节点的距离d_ij定义为从节点i到节点 j最少需经过的节点数，即最短路径边的数量。网络的平均路径长度L定义为任意两个节点之间的距离的平均值，即

网络的平均路径长度描述了节点间的分离程度，即网络有多小。

3.聚类系数

聚类系数表示的是一个图形中节点聚集程度的系数。在现实网络中，尤其是在特定的网络中，由于相对高密度的连接点关系，节点总是趋于建立一组严密的组织关系，这种可能性往往比两个节点之间随机建立一个连接的平均概率更大。这种相互关系可以用聚类系数进行量化表示。聚类系数表达的是成簇的固有趋势，比如在朋友关系网络中，你的朋友的朋友很可能也是你的朋友，你的两个朋友彼此很可能也是朋友。

我们可以将聚类系数C定义为一个节点的相邻节点，也可以定义为彼此的相邻节点。对于一个节点i，集群系数可以定义为

式中， k_i是节点i的度， E_i是这k_i个节点之间存在的边的数量。集群系数即与该节点相邻的所有节点之间连边的数量占这些相邻节点之间最大可能连边数量的比例。图2.20中显示了无向图中某个节点的聚类系数。

整个网络的聚类系数为C=，即所有节点聚类系数的平均值；也就是说，同一个节点的两个相邻节点仍然是相邻节点的概率有多大。只有在全连通网络（每个节点都与其余所有节点相连接）中，聚类系数才等于 1，一般聚类系数均小于 1。研究表明，规则网络具有大的聚类系数和大的平均路径长度，随机网络具有小的聚类系数和小的平均路径长度。事实上，在很多类型的网络中，你的朋友的朋友同时也是你的朋友的概率会随着网络规模的增加而趋于一个常数。表2.2中显示了2020年一些真实世界网络的部分统计特性。

如表 2.2 所示，真实世界网络普遍具有高的聚类系数和较短的平均路径长度，社交网络度分布普遍服从幂律分布。

4.其他特性

上述特性是复杂网络研究的基础，真实网络还存在下列统计特性。

（1）网络弹性（Network Resilience）。网络功能依赖于其节点的连通性，网络弹性表示为删除网络节点后对网络连通性的影响。删除网络节点的方式有两种：随机删除和有选择地删除。随机删除网络节点的分析方式称为网络的鲁棒性分析，有选择地删除网络节点的分析方式称为网络的脆弱性分析。研究表明，随机删除节点基本上不影响无标度网络的平均路径长度；相反，有选择地删除节点后，无标度网络的平均路径长度较随机网络的增长快得多。这表明无标度网络模型相对于随机网络具有较强的鲁棒性和易受攻击性。

（2）介数（Betweeness）。介数反映相应节点或者边在整个网络中的作用和影响力。介数分为边介数和节点介数，节点介数为网络中所有最短路径中经过该节点的数量比例，边介数同理。在社交网络中，介数反映不同人员的关系地位。

（3）度和聚类系数之间的相关性。不同网络结构之间的差异可以用网络中度和聚类系数之间的相关性来描述，该相关性包括不同度数节点之间的相关性和节点度分布与其聚类系数之间的相关性，前者描述网络中与高度数（或低度数）节点相连接的节点的度数是偏高还是偏低，后者描述高度数节点的聚类系数是偏高还是偏低。实证表明，在社交网络中，节点具有正的度相关性，节点度分布与其聚类系数之间具有负的相关性，其他类型的一些信息网络、生物网络等则相反。这说明这两种相关性可以用来区别社交网络和其他类型的网络。

2.3.2 网络演化模型统计特性

本节简要介绍规则网络、随机网络、小世界网络、无标度网络等不同网络演化模型，并分析这些网络的常用统计特性，观察它们之间的差异。

1.规则网络

最简单的网络是规则网络，此时系统中元素之间的关系可用一些规则的结构表示。假设真实世界中有这样一个平等模型，其中人们有相同数量的邻居，这显然不现实，但可以准确模拟真实世界的聚类系数。图 2.21 中显示了度为 4 的规则网络，其聚类系数为，平均路径长度为，其中c为平均度， n为节点个数。

规则网络具有大的聚类系数，但平均路径较大。聚类系数为定值，不能根据真实世界网络进行调整。

2.随机网络

从某种意义上讲，规则网络和随机网络是两个极端，复杂网络处在两者之间。节点按照某种自组织原则连线后，演化成各种不同的网络。对随机图而言，通常有两种定义方式。

·定义1 给定N和M，G₁（N，M）的定义是随机从N个顶点和M条边所生成的所有图集合中选择一个。

·定义2 给定N和p，G₂（N， p）的定义是有N个顶点，并且两个顶点之间以概率p∈[0，1]来决定是否连边。

事实上，这两种定义是等价的。1959年，Erdos和Rényi提出，在网络节点间可以按不变概率p随机地布置连线来有效地模拟通信科学和生命科学中的网络。这好比在地上撒一堆豆子，豆子之间是否用线来相连由某个概率值确定。在此模型中，节点的度分布服从泊松分布。随机网络具有小的平均路径长度，但聚类系数较小。一个随机图的聚类系数用p=表示，平均路径长度用表示。

3.小世界网络

规则网络和随机网络并不能很好地展现真实网络。小世界网络模型是一类既有较短平均路径长度又有较高聚类系数的网络，是复杂网络研究中的重大突破。简单地说，小世界效应是指在复杂网络结构中任意两点之间存在一条相对很短的连接路径，具有这种小世界效应的网络就是小世界网络（见图2.22）。20世纪60年代，美国哈佛大学的心理学家做了如下实验：把一定数量给波士顿（位于美国东部的马萨诸塞州）某证券经纪人的信件随机分发给内布拉斯加州（位于美国中部）的人，要求传递信件时只能通过自己的朋友或熟人，且每次传递要通过最可能使信件到达该经纪人手中的途径。该实验表明，确实有一些信件到达了经纪人手中，并且通过传递记录发现这些信件从布拉斯加到波士顿平均经过了 6 次传递。这一实验是六度分割理论的起源。地球上有76亿人，每两人最多通过6个人就能彼此相连，“小世界”由此得名。小世界效应在某一方面可以很好地反映现实网络的结构特征，且在疾病传播、网络搜索等问题研究中得到了应用。

在小世界模型中，假设参数p控制模型中的随机率。模型初始为规则格，然后以概率p的增加随机边，参数0≤p≤1代表模型的随机性。当p=0时，模型退回规则格；当p=1时，模型变为随机图。一般而言，规则格的聚类系数用C （0）表示，平均路径长度用L（0）表示，于是小世界模型的聚类系数可以表示为C（ p）≈（1-p）3C（0），与C（ p）不同， L（ p）没有具体的表示公式，本例中小世界模型的聚类系数为C（0.2）≈（1-0.2）3×=0.3072，而平均路径长度衰减得比聚类系数更快。实证表明，倾向于需要那些具有高聚类系数和较短平均路径长度的模型，所以p的取值范围为0.01≤p≤0.1。生成小世界网络的算法如表 2.3所示。

由图 2.22 可以看出，左边p=0 时，网络是规则网络，右边p=1 时，网络是随机网络，中间的网络是在规则网络上加一点随机因素而形成的小世界网络，它具有较大的聚类系数和较小的平均路径长度。大量实验表明，真实网络几乎都具有小世界效应，且大量真实网络节点度分布服从幂律分布。

在该算法中，重链是指使用节点v_i和v_k之间一条不存在的边，以p的概率代替节点v_i和节点v _j之间的已知边。

4.无标度网络

尽管小世界模型能很好地刻画现实世界的小世界性和高聚集性，但对小世界模型的理论分析表明，其节点的度分布仍呈指数分布。一般把节点度服从幂律分布的网络称为无标度网络，并称这种节点度的幂律分布为网络的无标度特性。无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性。无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性，人们发现无标度网络具有普遍性，社会网络、生物网络、贸易网络等各类网络都具有无标度网络特征。

5.随机聚类网络

社团的节点集满足一个简单的条件：属于同一个社团的节点有许多相互连接的边，而不同的社团由相对较少的边相连接。

在随机聚类网络的形成中，两个节点如果属于同一个社团，那么它们的连接概率为P_in，如果属于不同的社团，那么它们的连接概率为P_out。

在典型的随机聚类网络中， P_in值较大， P_out值较小，即社团内的节点连接紧密，而社团之间的节点连接稀疏。

评价社团检测技术优劣程度的Girvan-Newman算法基于如下的两个定义。

· Z_in/＜k＞，社团内节点的联系程度。

· Z_out/＜k＞，不同社团之间联系的紧密程度。

典型的随机聚类网络必须满足P_out≪P_in。

6.核心-边缘网络

网络可以采用局部网络、全局网络、中等标度网络的方法来描述。网络理论的一个主要目标是识别大型网络统计学意义上的主要结构，以便分析和比较复杂网络的框架。在这个目标下，中等标度网络结构的识别算法使得我们能够发现节点和边在局部网络及全局网络中不明显的特征。

通过计算确定核心-边缘网络的结构，可以划分哪些节点属于密集连接的核心节点，哪些节点属于外围稀疏连接的边缘节点。

网络的核心机构不仅是紧密相连的，而且往往是网络的中心。我们可以将单个社团视为网络核心结构的一部分，整个核心结构由多个社团组成，社团之间可以重叠。

7.确定性网络模型

除层次网络外，以上提及的模型都是随机的。随机性是产生具有小世界效应和幂律分布的复杂网络的共同特性，即新节点以不同的概率与系统中已有的节点进行连接。然而，如Barabasi等人所言，随机性虽然符合大多数现实网络的主要形成特性，但很难让人对复杂网络的形成及不同节点间的相互作用有直观和形象的理解。此外，随机模型中的概率分析方法和边的随机连接不适合具有固定节点连通度的通信网络，如神经网络、计算机网络和电路网络等。因此，以确定的方式构造小世界网络和无标度网络不仅具有重要的理论意义，而且具有重大的实际应用价值。确定性网络的一个重要优点是，人们可以解析计算网络的特性，如度分布、簇系数、平均路径长度和邻接矩阵等。

8.规则网络与随机网络的区别

一般把一维链、二维正方晶格等称为规则网络。规则网络是指平移对称性晶格，其中任何一个格点的近邻数量都是相同的。随机网络是另一个极端，在由N个顶点构成的图中，可以存在条边，从中随机连接M条边所构成的网络就称为随机网络。另一种生成随机网络的方法是，给定一个概率p，对于中的任何一个可能的连接，都尝试一遍以概率p的连接。若选择M=，则这两种随机网络模型就可以联系起来。对于此类随机网络模型，其几何性质的研究并不简单。

规则网络与随机网络的典型几何性质包括度分布、平均集聚程度与平均最短距离。规则网络的所有顶点都相同，因此其度值相同，度分布为δ（k-k₀ ），平均集聚程度也只需要在一个点计算C=〈C_V〉=C_V，最短距离也可只从某个顶点开始，首先计算从它到所有其他顶点之间的距离之和满足L～N2，然后计算平均值d=LN/（2×）～N。随机网络G（N， p）包含从空图到完全图的所有可能情况，因此，随机图的几何性质需要对每种可能的图进行平均，例如首先计算每种可能图的最短距离，然后按照各自出现的概率进行平均。研究结果表明，随机网络顶点的度值符合平均值为pN 的泊松分布，集聚程度约等于p，最短距离满足d～ln（ N）。

对比规则网络与随机网络，平均集聚程度与平均最短距离这两个静态几何量能够很好地反映规则网络与随机网络的性质及差异。规则网络的特征是平均集聚程度高而平均最短距离长，随机网络的特征是平均集聚程度低而平均最短距离短。规则网络的平均最短距离满足d～N，而其集聚程度依赖于近邻数量k₀。

然而，正是由于其集聚程度非常小，所以其平均最短距离短。考察一个顶点μ的近邻，假设其近邻数为a，那么在a个近邻的近邻之中，相互重复的个数非常少，所以从μ出发经过两次近邻关系可以找到正比于a2的新顶点，最多经过log_a N 个近邻关系就可以穷尽整个网络。所以，其最短距离满足d～ln（N）。可见，对于规则网络，正是由于其集聚程度高、重复率很大，所以平均最短距离大。