复杂网络的连通性

  • Post author:
  • Post category:其他

一、无向网络中的巨片

许多实际的大规模复杂网络都是不连通的,但是往往会存在一个特别大的连通片,它包含了整个网络中相当比例的节点,这一连通片称为巨片。如下图所示
在这里插入图片描述
一些关于网络拓扑性质的研究往往是针对巨片来研究的。

二、有向网络中的蝴蝶结结构

实际的大规模有向网络往往既不是强连通也不是弱连通的,但是许多有向网络往往有一个包含了网络中相当部分节点的很大的弱连通片,称为弱连通巨片。这一弱连通巨片又往往具有一种包含4个部分的蝴蝶结结构。
在这里插入图片描述
(1)强连通核( Strongly connected core, SCC):也称为强连通巨片,它位于网络的中心。SCC中任意两个节点之间都是强连通的,即存在从任一节点到另一节点的有向路径。
(2)入部(IN):包含那些可以通过有向路径到达SCC但不能从SCC到达的节点。也就是说,一定存在从IN中任一节点到SCC中任一节点的有向路径;反之,从SCC中任一节点出发沿着有向边都无法到达IN中的一个节点。
(3)出部(OUT):包含那些可以从SCC通过有向路径到达但不能到达SCC的节点。也就是说,一定存在从SCC中任一节点到OUT中任一节点的有向路径;反之,从OUT中任一节点出发沿着有向边都无法到达SCC中的一个节点。从IN中任一节点到OUT中任一节点必然存在有向路径,而且该路径必经过SCC中的某些节点。
(4)卷须(Tendrils) :包含那些既无法到达SCC也无法从SCC到达的节点。对于挂在IN上的任一卷须节点,必至少存在一条从IN中某一节点到该节点的不需经过SCC的有向路径;对于挂在OUT上的任一卷须节点,必至少存在一条从该节点到OUT中某一节点的不需经过SCC的有向路径。此外,还有可能存在从挂在IN上的卷须节点到挂在OUT上的卷须节点的不经过SCC的有向路径,这些串在一起的卷须节点称为管子(Tube)。


版权声明:本文为weixin_42374938原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。