无向网络中的巨片（Giantcomponent）-有向网络中的蝴蝶结结构（Bow-ties。。。

⽆向⽹络中的巨⽚（Giantcomponent）-有向⽹络中的蝴蝶结结构（Bow-ties。。。

⽬录

尽管⽹络科学和传统的图论关于基本概念的定义是⼀致的，但两者在研究⾓度和研究⽅法上有着重要的区别。

传统的图论往往着眼于具有某种规则结构或者节点数较⼩的图，因⽽往往在理论分析时可以采⽤图⽰的⽅法直观地看出图的某些性质(如是否连通)。

然⽽，近年⽹络科学研究中涉及的实际⽹络往往包含数⼗万甚⾄数百万以上的节点，⽽且具有复杂的不规则拓扑结构。对于如此⼤规模的⽹络不可能通过图

⽰的⽅法看出⽹络的拓扑性质，⽽必须借助于强⼤的计算能⼒和统计⽅法。

此外，⽹络科学不仅关注拓扑结构，⽽且更为关注拓扑结构的演化及其与⽹络上的动⼒学⾏为之间的关系等。

⽹络规模尺度上的巨⼤差异使得传统图论和⽹络科学对所研究的相关问题的表述都会不⼀样。

例如，在图论中，如果去除某个顶点就使得⼀个图从连通变为不连通，那么该顶点就称为割点(Cut-vertex) ;如果去除某条边就使得⼀个图从连通变为不连通，那

么这条边就称为桥( Bridge)。

但是，在规模巨⼤的复杂⽹络中，去除单个节点或单条边往往并不能对⽹络的拓扑性质(如连通性)产⽣如此⼤的本质影响。

因此，⽹络科学更为关⼼的是：要去除⽹络中多少⽐例的节点或者边才能对⽹络的某个性质(如最⼤连通⽚的⼤⼩)产⽣本质影响？不同的去除策略是否会产⽣显

著不同的后果？对⽹络的某种性质如何提⾼其对节点和边的去除鲁棒性？等等。

从更⼀般的科学范围看，研究个体数量较少的系统和研究个体数量极⼤的系统往往采⽤不同的⽅法：在物理学中，前者可以采⽤精确的⽅法，如经典⼒学；后者

则往往需要采⽤统计的⽅法，如统计⼒学。对于这种差异，经典的陈述是诺贝尔奖得主、物理学家Anderson于1972年在《Science》上发表的⼀篇挑战还原论

的经典⽂章“多则不同( More is different)”。⽂中⽴场鲜明地指出:

“由⼤量基本粒⼦构成的复杂系统的集体⾏为谢字开头的成语 并不能依据少数粒⼦的性质做简单外推就能理解。正好相反,在复杂性的每微博怎么设置自动回复 ⼀个层次都会呈现全新的性质,⽽要理解这

⼀⾏为所需要做的研究,就其基础性⽽⾔,与其他研究相⽐毫不逊⾊。”

从哲学的观点看，这就是从量变到质变。例如，单个铜原⼦是不会导电的，因为电⼦被原⼦核拉住了。然⽽，由数量巨⼤的铜原⼦构成的⼀根铜丝却能导电。这

种导电特性就是巨量的铜原⼦聚合之后所涌现出的⼀种新的与单个铜原⼦完全不同的特性。⽇常⽣活中有许多这样的由数量巨⼤的个体组成的系统会涌现出与单

个个体不同的性质的例⼦。

近年来，⼈们在刻画复杂⽹络结构的统计特性上提出了许多概念和⽅法，并且利⽤了统计物理中的许多⽅法，包括相变和渗流理论、平均场理论、主⽅程⽅法

等。2002年 Barabasi和 Albert发表的综述⽂章的标题就是“复杂⽹络的统计⼒学”。

复杂⽹络的连通性

⽆向⽹络中的巨⽚(Giant component)

⽹络平均距离和直径等概念严格说来只有对于连通图才是有限值。

经验和实证研究表明，许多实际的⼤规模复杂⽹络都是不连通的，但是往往会存在⼀个特别⼤的连通⽚，它包含了整个⽹络中相当⽐例的节点，这⼀

连通⽚称为巨⽚( Giant component) 。

如下图所⽰，具有单个连通巨⽚的⽹络⽰意：

⼀些关于⽹络的拓扑性质的研究往往是针对巨⽚来进⾏的。实际⽹络中不仅往往存在巨⽚，⽽且巨⽚⼏乎总是唯⼀的。这⼀点仍然可以通过对社会⽹络的直

觉来推断。假设社会⽹络中存在两个巨⽚，每个都包含数以千万计甚⾄数以亿计的⼈，只要某⼀天分别属于两个⽚的两个⼈偶然相识，也就在这两个⽚之间对应

地有⼀条边相连，那么这两个巨⽚就合并成为了⼀个更⼤的巨⽚。

再有⼀个实例是全球最⼤的社交⽹站Facebook上的活跃⽤户之间的朋友关系⽹络。

2011年5⽉, Facebook 上⼤约有7.21亿个活跃⽤户以及687亿条朋友关系链，节点数超过当时全球⼈⼝的10%。

这⾥，如果⼀个Facebook注册⽤户在2011年5⽉测量数据之前的最近28天时间⾥⾄少登录过⼀次并且⾄少有⼀个Facebook朋友，那么就称该⽤户为活跃⽤户，

这⾥把那些只是注册过但⼏乎从不使⽤或者没有朋友的孤⽴⽤户剔除掉。

对于⼀个包含多个连通⽚的⽹络，可以绘制该⽹络的连通⽚规模的分隐患排查制度 布。

下图给出了双对数坐标下Facebook ⽹络中不同规模的连通⽚的数量。图中最右端的⼀个⿊点对应于最⼤的连通⽚(即巨⽚)，它包含了⽹络中99.91%的节点。其

余的连通⽚数量很多但规模都很⼩，第⼆⼤连通⽚仅包含不到3 000个节点。

有向⽹络中的蝴蝶结结构(Bow-tie structure)

实际的⼤规模有向⽹络往往既不是强连道路交通安全法56条 通也不是弱连通的，但是许多有向⽹络往往有⼀个包含了⽹络中相当部分节点的很⼤的弱连通⽚，称为弱连通

巨⽚( Giant weakly connected component,GWCC)。这⼀弱连通巨⽚⼜往往具有⼀种包含4个部分的蝴蝶结结构(Bow-tie structure) :

强连通核( Strongly connected core , SCC)

也称为强连慈善英语 通巨⽚(Giantstrongly connected component)，它位于⽹络的中⼼。SCC中任意两个节点之间都是强连通的，即存在从任⼀节点到另⼀

节点的有向路径。

⼊部(IN)

包含那些可以通过有向路径到达SCC但不能从SCC到达的节点。

也就是说，⼀定存在从IN中任⼀节点到SCC中任⼀节点的有向路径；反之，从SCC中任⼀节点出发沿着有向边都⽆法到达IN中的⼀个节点。

出部(OUT)

包含那些可以从SCC通过有向路径到达但不能到达SCC的节点。

也就是说，⼀定存在从SCC中任⼀节点到OUT中任⼀节点的有向路径；反之，从OUT中任⼀节点出发沿着有向边都⽆法到达SCC中的⼀个节点。

从IN中任⼀节点到OUT中任⼀节点必然存在有向路径，⽽且该路径必经过SCC中的某些节点。

卷须(Tendrils )

包含那些既⽆法到达SCC也⽆法从SCC到达的节点。

对于挂在IN上的任⼀卷须节点，必⾄少存在⼀条从IN中某⼀节点到该节点的不需经过SCC的有向路径；

对于挂在OUT上的任⼀卷须节点，必⾄少存在⼀条从该节点到OUT中某⼀节点的不需经过摘抄优秀作文10篇 SCC的有向路径。

此外，还有可能存在从挂在IN上的卷须节点到挂在OUT上的卷须节点的不经过原因的英文 SCC的有向路径，这些串在⼀起的卷须节点称为管⼦(Tube)。

下表和下图说明的是超过2亿个页⾯和15亿个链接的WWW样本的蝴蝶结结构。

在 WWW 样本上：

包含30%左右⽹页的强连通核,对应于可以通过⿏标点击超链接在有限步内互相到达的“核⼼⽹页”。

包含24%左右⽹页的⼊部，对应于可以通过超链接在有限步内到达“核⼼⽹页”但是⽆法返回的“源⽹页”。

例如，你设计的⼀个⽹页上有超链接指向某个“核⼼⽹页”，但通常并不存在从“核⼼⽹页”指向你的⽹页的超链接。

包含24%左右⽹页的出部对应于从“核⼼⽹页”的链接中指出来却⽆法回到“核⼼⽹页”的“⽬标⽹页”。

例如，你在搜索⽂章时，从Google 主页开始，找到某位教授的主页，然后找到该教授的⽂章列表，然后点击相应的⽂章。但是你从该⽂章对应的页⾯通常⽆法

通过超链接再返回到Google主页。

当然，强连通核未必⼀定就是蝴蝶结结构中节点数最多的部分。

例如，Vitali等⼈研究了由全球43060家跨国公司基于股权所有关系构建酱香牛肉的做法 的有向的经济⽹络，在该⽹络的蝴蝶结结构中，出部是最⼤的部分，⽽强连通⽚只占很⼩

部分。蝴蝶结也是⽣物⽹络中常见的⼀种结构”。从更⼀般的意义看，蝴蝶结作为复杂的技术和⽣物⽹络中常见的⼀种系统结构可能有助于在效率、鲁棒性和进

化能⼒等⽅⾯保持⼀种平衡。

参考：

[1] 汪⼩帆,李翔,陈关荣.⽹络科学导论[M].北京:⾼等教育出版社,2012