系统科学大百科全书

复 杂 网 络 词 条

1,  网络世界

我们身处网络世界。我们处在一个由世间万物构造而成的复杂网络世界之中。我们的世界充满了彼此是复杂系统之网络构造的相互联系。千千万万的物理、社会、生物、自然、人类、经济、文化、历史、……系统无不可以用纷纭复杂的网络来描述刻画和模拟研究。网络科学已经越来越广泛地被接受为数据驱动的跨学科科学。

图1--图9给出人们常见的一些复杂网络例子。

 (图1-7,取自香港城市大学陈关荣教授学术报告)

图1: 万维网(WWW 引自 K.C.Claffy)

图2 互联网(Internet,引自William R. Cheswick)

图3，全球电信网络

图4 航空线网络

图5 各种生物网络

图6大规模集成电路（VLSI Circuits ）

图7  美国有线电视新闻网（Cable News Network）

图8 分子生物学网络

图9 科学家合作网络

2, 复杂系统的网络图像

对于包含大量元素的复杂系统 (complex system)，系统集体涌现出的动力学现象，无法通过个体视角来解释。例如 SARS病毒的爆发传播、大规模停电故障等.要理解这些现象，需从基础的组成元素间的相互作用入手。凝聚态物理中，我们有量子力学描述各种材料中原子等粒子间的相互作用；面对广泛多样、多自由度、非线性，带有复杂性(complexity)的系统，网络或者说图 (graph)成为刻画复杂系统内部相互作用关系的语言。一个网络是由节点和连边构成的集合。例如万维网，节点代表网页，连边表示超链接；社交网络，节点对应着个人，连边代表朋友关系；细胞内的代谢网络，节点为代谢物，连边描述之间的化学反应；根据词语在文本中的共现、论文间的引用、科学家之间的合作等也可构造网络。尽管这种抽象和简化忽略了许多信息，对于复杂系统而言，网络被证明是一次概念和方法论上的飞跃。网络成为大规模集群组织的方式和存在的形态。在这样去中心化(decentralized)的自组织结构上，没有明显的中心和边界，每个节点显得既重要也不重要。每个节点都可以借助其他节点，通过级联传播等方式和远方节点发生作用。

尽管大量真实网络久已存在，社会学家早已研究过小规模的社会网络，图论也很古老，但复杂网络研究的兴起却推迟到上个世纪末。真实世界的网络有着怎样的连接模式？物理学中，网络的形象通常是简单规则的，比如晶格；数学上有Erdős-Rényi (ER)随机图模型，假设节点间的连接是随机的。随着大数据时代的到来，海量数据唾手可得。数据是推动复杂网络研究的催化剂，正如加速器之于粒子物理带来的影响。数据会说话，允许绘出真实网络，揭示连接结构，将我们从对真实网络的无知和猜想中解放出来。网络所能描述的系统相当广泛，横越自然、社会、技术系统。巨大的差异下，相应的网络却呈现出一些共同的结构模式，社交网络里发现的组织特征同样可以在细胞等网络中找到。另一方面，分散在不同学科看似不相关的问题，实质上可归为网络上的同一类问题。例如网络的渝渗模型可以解释大规模停电、因特网故障瘫痪、预测金融系统的崩溃；病毒的传播、文化信息的扩散、人群骚乱的爆发都可以用网络上的传播模型来理解。这些共通性凝聚了来自物理学、数学、计算机、生物、社会科学等共同的兴趣，经过十几年“野蛮”生长，形成了跨越多学科藩篱、交叉性极强的网络科学。

如今网络科学已在众多领域产生了深刻影响。以下仅举几个例子。输运网络模型可以解释叶脉纹理、血管的生长。细胞内的蛋白质、基因调控网络为疾病治疗提供了新线索。绘制哺乳动物大脑内数千亿神经元构成的网络则是一项雄心勃勃的研究，将帮助我们从系统层面理解大脑活动。网络鲁棒性研究可以告诉我们如何构造容错稳定的因特网络电力网等。网络间的相依性研究则可揭示社会经济系统的脆弱性，为金融崩溃预警，经济政策治理等提供新思路。网络上的传播模型则可揭示病毒信息传播、文化技术扩散机制，如何防控传染病，如何制造病毒式传播进行市场营销。网络科学的发展在方法论上革新了社会科学，诞生了计算社会科学(computational social science)。强大的网络分析技术允许我们利用收集的数据推断重构未知网络，找出关键节点，甚至控制网络。

3，网络的拓扑结构与聚类系数

尽管复杂系统涉及的对象相当广泛多样化，在复杂网络的框架下，它们表现出许多共同的结构特征。寻找、刻画和度量这些基本特征的努力自网络科学发轫以来曾未停止。这里简要介绍几个复杂网络的局域和宏观特征。

数学上网络用邻接矩阵 (adjacencymatrix) A表示，矩阵元 a_ij= {0, 1}。若节点 i，j之间有连边，则矩阵元为 1，反之置 0。对于无向（双向） 网络 a_ij=a_ji； 对于有向网络，如万维网、引文网络，矩阵元为1表示存在相应的取向边。节点的度 k，定义为与此节点相连的边数之和。对于N个节点的网络,第 i节点的连边数目为:

k_i=∑_j=1^N a_ij

聚类系数:

社交网络中，朋友的朋友也是朋友的现象，可用簇或聚类数(clustering coefficient)

来刻画，反映了社会网络的同质化 (homophily)。节点 i的聚类系数定义为

C_i=n_i/ C_{k i} ²=2n_i / k_i(k_i-1)

其中 C_{k i} ²、n_i分别指节点i的邻居间连边数最大值和实际值，因此聚类系数表达了节点的邻居也互为邻居的概率。或者说一个人的许多朋友，彼此之间也为朋友的概率。

图 10  (a) ER网络度分布。随着 ⟨k⟩增大， P (k)由泊松分布逐渐演变成高斯分布。 (b)双对数坐标下的无标度分布。BA网络：γ =3；因特网 γ=2.2。

4      网络的无标度特征

在网络数据可以大规模获取之前，通常用 ER随机图模型描述网络。 ER随机网络假设任意两个节点之间的连接是随机的，与节点的属性无关。

有两种构造方式：G(N,p)正则系综模式，任意一对节点间存在连边概率为p，共有

⟨M⟩=N(N−1)p/2

条连边；

或者 G(N,M)微正则系综模式，随机选取一对节点，并添加连边，共添加 M条，p=2M/N(N−1)。度分布 P(k)是一个二项式分布

       P(k)=C _N−1 ^kp^k(1 −p)^N−1−k

当 N很大 p很小时， P (k)退化成泊松分布：

P (k) = (z^k /k!)e^−z

这里

        z = ⟨k⟩=2⟨M⟩/N =(N −1)p ≃Np

多数节点的度集中在z附近，P(k)在P(z)处取得峰值，如图10 (a)所示。

二阶矩

方差

        σ² =⟨k²⟩−⟨k⟩² =(1 −p)⟨k⟩≃⟨k⟩

因此，我们说ER随机网络是均质的 (homogeneous)。

度为k的节点的邻居的度的平均值为

所以，分支系数 (branching factor)，即平均每个节点的邻居向外扩展的节点数目为

κ = k_nn(k) −1= ⟨k⟩−p ≃⟨k⟩

这要求

由此得出网络直径（网络上两个节点间最远距离）

D ≃ ln N /ln ⟨k⟩

⟨k⟩决定了网络的状态：当⟨k⟩<1时，D→∞，网络中充满孤立节点或碎片；

当每个节点平均至少有一条连边，即 ⟨k⟩=1时，达到渝渗临界值，网络中出

现连通巨片 (giant connected component)。

当⟨k⟩>1时，ER网络是小世界网络（见下节）；

当⟨k⟩～lnN时，D≃1，网络成为一个全图。聚类系数

C(k)= pC_k ²/C_k ² =p = ⟨k⟩/N

是个微弱的小量，并且独立于节点的度，因为ER网络是一个稀疏均质的网络。

ER随机网络多大程度与真实网络相符？真实网络上节点间的连接显然很大

程度上不是随机的。 ER随机网络虽然成功再现了小世界特征（见下节），

但其他方面与实际情况并不相符。真实网络中，一般聚类系数C(k)随 k增

大而减小，例如在代谢网络中 C(k)～k⁻¹。上式与预言不符。更关键

的是，大量真实网络数据显示其度分布并不是的泊松分布，而是带有胖尾的

分布 (fat-taileddistribution)，见图10 (b)。这给真实网络带来一系列特殊的性

质。例如，对于随机故障非常鲁棒，而在针对大度节点的攻击下又非常脆弱。数学上用幂律近似：

P (k) ～k^−γ (2<γ< 3).

对于真实世界的网络，一般 2<γ<3。如下计算可给出解释：

⟨k⟩～k_max^2−γ

k_max是网络中度的最大值。因此，γ> 2时，⟨k⟩才不会散。 ⟨k²⟩～k^3−γ ，可见 γ<3时，⟨k²⟩发散，导致方差 σ²=⟨k²⟩−⟨k⟩²也发散，度分布极其不均匀，网络是异质的 (heterogeneous)。在经济学中，这种分布模式又用来反映社会财富分配不均。

表 1  ER随机网络和无标度网络 (SF)的比较。

ER随机网络上，节点的度集中在 ⟨k⟩附近 ,其取值决定了网络的连接状况，是 ER网络的特征标度 (characteristic scale)。而对于幂律分布的网络，不存在这样的特征标度，故又称无标度网络(scale-free)：一方面，标度不变性意味着所有的标度都是等价的，不存在特殊的标度；另一方面，幂律分布使得度分布不均匀、涨落大，多数节点的度达不到⟨k⟩。

图 10 显示两种度分布方式还有一个重大差别： ER随机网络上缺乏度非常大的节点(hub)，泊松分布使得 P (khub)衰减的比指数还快。而对于无标度分布，P (k_hub)以幂律缓慢衰减，导致网络上大度节点的比例不可忽略。真实网络上有丰富的大度节点，呈胖尾状分布。从度最大值kmax(N)的行为中，也可以找到解释。考虑自然截断

即最多找到一个度在 k_max以上的节点。

对于无标度网络，

k_max～ _N1/(γ−1)

对于 ER随机网络，令 P (k)指数衰减，得到

k_max～⟨k⟩+ clnN

这说明即使是大规模的随机网络，k_max 相对来说仍然很小。两种网络的差异总结，见表1。

5  网络的小世界特征

地球上任意两个人需要几个中间人才能找到对方？有一种有趣的回答“六度分隔”：尽管我们身处的社交网络规模巨大，人与人之间分隔距离是六。这种现象称为小世界(small-world)效应。 1967年，社会心理学家 Milgram在 Pool和 Kochen理论工作的基础上首次通过实验检验了社会网络的小世界效应：随机选取一拨人，让他们把信件传递到指定的地址。每个人把信件传递给接近目标地址的人。信件沿着熟人关系链平均传递六次即可到达目标。如今通过互联网在线的方式，例如转发邮件，进一步验了证小世界现象。小世界的概念虽然源于社会网络，但普遍适用于其它各类真实网络，是复杂网络的基本特征。小世界一般指大规模的网络上，节点间的平均距离⟨ℓ⟩相对很短，和网络规模呈对数关系：

⟨ℓ⟩～ ln N

Watts-Strogatz (WS)模型（见图 11）和 ER网络都成功复现了小世界特征，其中的关键是引入随机化的长程连边 (shortcuts)。它们连接了远方的节点，带来了小世界效应。而小世界进入人类社会，得益于遍布全球的海空航运网络以及互联网。小世界对疾病信息传播产生重大影响。历史上欧洲的黑死病波状扩散，说明人类还未进入全球性的小世界文明。如今，SARS、禽流感等病毒通过航空网络跳跃式的在全球迅速扩散。

图 11 网络从规则到随机的过渡。 p较小时，网络介于规则和随机之间，兼具高聚类系数和小世界特征，称为 WS小世界网络。 p=1，网络完全随机化，变成 ER随机网络。

Milgram实验以及 Kleinberg对小世界导航问题研究表明小世界性质使得大规模的网络可搜索：利用局域信息（已知所处节点的邻居以及它们距离目标节点的距离），和贪婪算法（每一步基于局域信息向离目标最近的邻居移动）可通过较短路径到达目标节点。

WS模型介于有序和无序之间，符合通常的物理兴趣取向。但 WS、ER模型中缺乏大度节点，背离了真实网络。对于 2<γ<3的无标度网络，二阶矩 ⟨k²⟩发散，网络上丰富的大度节点，极大缩短了节点间距离：任意两个节点通常只隔着几个中间大度节点。这样的网络比小世界网络还“小”，被称为超小世界 (ultrasmall-world)：

⟨ℓ⟩～ln ln N.

如果全球 70亿人构成超小世界，那么人与人之间是惊人的“三度分隔”。

6  网络的社团结构

社团 (community)的研究可上溯到图论中图的分割问题，诸如芯片上大规模集成电路排线布局优化。社团结构本身没有十分明确的定义，一般指网络中连接密集的子图，而社团之间的连接比较松散（见图12）。这种疏密特征可用模块度来刻画:

只计算社团内部连边数目。大的模块度 Q值意味着一个好的划分。其中 s_i 指节点 i  所属社团。 社团代表了网络上大尺度结构，实际网络上社团对应着有实际意义的结构单元：在社交网络上，社团是特定的朋友圈；在生物网络上，社团是某种功能模块。根据节点间的连接模式而划分社团，能够挖掘出许多蕴藏在节点间连接模式中的有价值信息。例如空手道俱乐部朋友关系。

网络的社团结构分析成功预测了俱乐部的分裂（图 12(a)）；根据政治博客链接关系识别出博主的政治倾向；对于科学家合作网络，社团反映出以研究兴趣为主导的合作关系，以及相关领域研究人员的组织结构（图 12(b)）。社团划分方法众多，例如分级聚类 (hierarchicalclustering)、谱聚类方法、模块度最大化 (maximum modularity)、统计推断等）。它们不是单一方法，而是一个方法家族。

社团具有层次性，即大的社团由小的社团构成，小的社团又可以分解成

更小的社团;社团具有重叠性，有相当数量的节点同属于多个社团（图 12(c)）。在社交网络上，人们处在同质化 (homophily)的社团里 ,社团内部的连边反映了强关系；而社团之间的连边属于弱链接 (weak ties)，具有意想不到的作用：弱链接是沟通不同的社会圈子的桥梁，带来多元信息。弱链接对于文化技术等传播扩散极为重要。并且弱关系的丰富性，即社交多样性和个人的富有程度正相关。

图 12 社团结构识别，不同颜色代表不同社团。 (a)Zachary空手道俱乐部网络，通常被用来检验社团识别算法是否准确。 (b)圣塔菲研究所科学家合作网络。 (c)社团重叠以及层次性示意图。

词条编写者：汪秉宏，魏宗文

2018-2