网络基本拓扑性质
3.1 引言
本章和下一章介绍刻画网络结构的一些拓扑性质。从网络结构角度看,我们首先关心的是网络中的节点是否是连在一起的,也就是网络的连通性问题。而网络的许多其他拓扑性质(例如平均距离)的计算也依赖于网络的连通性。因此,本章首先介绍的就是人们对于实际网络的连通性的认识。在介绍了关于单个节点的最基本的属性——节点度的概念之后,本章将重点阐述近年网络科学研究中关注最多的3个拓扑性质:平均路径长度、聚类系数和度分布。
3.2 复杂网络的连通性
3.2.1 无向网络中的巨片
网络平均距离和直径等概念严格说来只有对于连通图才是有限值。经验和实证研究表明,许多实际的大规模复杂网络都是不连通的,但是往往会存在一个特别大的连通片,它包含了整个网络中相当比例的节点,这一连通片称为巨片( Giant component)。 如图3-1所示。一些关于网络的拓扑性质的研究往往是针对巨片来进行的。实际网络中不仅往往存在巨片,而且巨片几乎总是唯一的。这一点仍然可以通过对社会网络的直觉来推断。假设社会网络中存在两个巨片,每个都包含数以千万计甚至数以亿计的人,只要某一天分别属于两个片的两个人偶然相识,也就在这两个片之间对应地有一条边相连,那么这两个巨片就合并成为了一个更大的巨片。
对于一个包含多个连通片的网络,可以绘制该网络的连通片规模的分布。图3-2给出了双对数坐标下Facebook 网络中不同规模的连通片的数量。图中最右端的一个黑点对应于最大的连通片(即巨片),它包含了网络中99.91%的节点。其余的连通片数量很多但规模都很小,第二大连通片仅包含不到3 000个节点。
3.2.2 有向网络中的蝴蝶结结构
实际的大规模有向网络往往既不是强连通也不是弱连通的,但是许多有向网络往往有一个包含了网络中相当部分节点的很大的弱连通片,称为弱连通巨片(Giant weakly connected component,GWCC)。这一弱连通巨片又往往具有一种包含4个部分的蝴蝶结结构(Bow-tie structure)(图3-3 ) :
(1）强连通核(Strongly connected core , sCC):也称为强连通巨片( Giantstrongly connected component),它位于网络的中心。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)。
当然,强连通核未必一定就是蝴蝶结结构中节点数最多的部分。
蝴蝶结也是生物网络中常见的一种结构”。从更一般的意义看,蝴蝶结作为复杂的技术和生物网络中常见的种系统结构可能有助于在效率、鲁棒性和进化能力等方面保持―种平衡。
3.3 节点的度与网络稀疏性
3.3.1 度与平均度
度(Degree)是刻画单个节点属性的最简单而又最重要的概念之一。
3.3.2 出度与入度
有向网络中节点的度包括出度(Out-degree)和入度( In-degree)。节点i的出度k（out）是指从节点i指向其他节点的边的数目,节点i的入度k（in）是指从其他节点指向节点i的边的数目。
从有向网络的定义看,上式是显然成立的。而且,它代表了一类复杂系统的一个重要特性:对于系统中每个个体而言不一定成立的性质,却会在整个系统的层面上成立。
3.3.3 网络稀疏性与稠密性
一个包含N个节点的网络的密度( Density )ρ定义为网络中实际存在的边数M与最大可能的边数之比。 因此,对于无向网络,我们有 对于有向网络,上式分母中的1/2去掉即可。
实际的大规模网络的一个通有特征就是稀疏性:网络中实际存在的边数要远小于最大可能的边数。
在分析网络模型时,如果当N→∞时网络密度趋于一个非零常数,就表明网络中实际存在的边数是与N2同阶的,那么我们就可以认为该网络是**稠密的**;此时,邻接矩阵中非零元素的比例也会趋于一个常数。而如果当**N→∞时网络密度趋于零或者网络平均度趋于一个常数**,就表明网络中实际存在的边数是比N@低阶的,那么该网络就是稀疏的;此时,邻接矩阵中非零元素的比例也会趋于零。
将时刻t网络中的节点数和边数分别记为N( t)和M( t)。如果两者呈线性比例关系,即M(t)~N(t),那么由式(3-11)可见,平均度〈k〉为一常数。另一方面,如果两者呈平方关系,即M( t) ~N^2( t),那么就意味着,平均而言,每个节点都会与网络中一定比例的其他节点直接相连,整个网络会演化为一个非常稠密的网络。研究表明,许多实际网络的演化是介于上述两种情形之间的,即服从如下的超线性关系,也称为稠密化幂律:
3.4 平均路径长度与直径
3.4.1 无权无向网络情形
1. 平均路径长度
网络中两个节点i和j之间的最短路径( Shortest path)也称为测地路径(Geodesic path),是指连接这两个节点的边数最少的路径。节点i和j之间的距离d,定义为连接这两个节点的最短路径上的边的数目,也称为两个节点之间的测地距离(Geodesic distance)或跳跃距离( Hop distance)。 注意到两点之间的最短路径可能不存在、可能只有一条、也可能有多条,但是两点之间的距离是唯一的,要么为有限值(如果存在最短路径),要么为无穷大(如果不存在最短路径)。我们在第2章已经介绍了可以利用广度优先搜索算法求得从一个节点到网络中所有节点的最短路径。一个含有N个节点和M条边的网络的平均路径长度可以用时间量级为O(MN)的广度优先搜索算法来确定。
大型实际网络往往是不连通的,此时,可能两个节点之间不存在连通的路径,即意味着这两个节点之间的距离为无穷大,从而导致整个网络的平均路径长度也为无穷大。为了避免在计算时出现这种发散问题,可以把网络平均路径长度定义为存在连通路径的节点对之间的距离的平均值。这种方法对于存在一个包含相当部分节点的连通巨片的网络较为适合。另一种方法是把平均路径长度定义为网络中两点之间距离的简谐平均( Harmonic mean) :
以上是计算平均值的两种方法
按照上式计算,两点之间距离为无穷大对应于距离的倒数为零,由此得到的平均路径长度总是有限值。如果我们认为两个节点之间距离越短,在它们之间发送信息的效率越高,也就是假设两节点之间发送信息的效率与它们之间距离的倒数成正比,那么式(3-15)中的GE就定量反映了网络中节点之间发送信息的平均效率,因此GE也称为全局效率(Global efficiency)。
2. 网络直径
网络中任意两个节点之间的距离的最大值称为网络的直径(Diameter),记为D,即
进一步地,我们可能更为关心的是网络中绝大部分用户对之间的距离。为此,可以统计网络中距离为d的连通的节点对的数量占整个网络中连通的节点对数量的比例,记为fd);并进而统计网络中距离不超过d的连通的节点对的数量占整个网络中连通的节点对数量的比例,记为g( d)。
研究表明,许多实际网络的直径和有效直径都呈现越来越小的趋势,也称为直径收缩( Shrinking diameters)现象。
以上是直径和有效直径的对比。
3.4.2 加权有向网络情形
对于加权无向网络,两个节点之间的最短路径定义为连接这两个节点的边的权值之和最小的路径。两个节点之间的距离即为最短路径上边的权值之和。
对于加权有向网络,从节点A到节点B的最短路径是指从节点A到节点B的权值之和最小的有向路径。
注意点：
在加权网络中,两个节点之间边数最少的路径并不一定是权值之和最小的路径。 在有向网络中,从节点A到节点B的距离可能并不等于从节点B到节点A的距离,甚至可能存在从节点A到节点B的有向路径但是不存在从节点B到节点A的有向路径。
最短路径问题 — Dijkstra算法详解 视频讲解最短路径查找—Dijkstra算法
3.5 聚类系数
3.5.1 无权无向网络情形
以上是基于无权网络
三角形的社会学意义是你的两位朋友也互相为朋友,从而3人之间形成一个三角形。因此,在社会学中是用网络中三角形的相对数量来刻画网络的聚类特性,也称横截性( Transitivity)。网络聚类系数的社会学定义如下:
网络聚类系数的两个定义(3-24)和(3-25)并不完全等价。定义(3-24)中的平均是对于每个节点聚类系数给以相同的权,而定义(3-25)中的平均则是对于网络中的每个三角形给以相同的权。与度小的节点相比,度大的节点可能被包含在更多的三角形中。然而,两种定义的差别并不会带来本质的影响,因为我们通常关心的是聚类系数的相对大小而不是绝对大小。
相对而言,聚类系数定义(3-24)易于数值计算,因而被广泛用于实际网络数据分析,而聚类系数的社会学定义(3-25)则更为适于解析研究。
在网络科学研究中有时会关注一类节点的整体行为或平均行为。在求得各节点聚类系数的基础上,我们可以得到度为k的节点的聚类系数的平均值,从而把聚类系数表示为节点度的函数:
3.5.2 加权网络情形
事实上,近年人们提出了多种加权网络的聚类系数的定义,其区别主要在于到底应该如何定量刻画边的权值对聚类特性的影响。
与无权网络聚类系数定义相比,上述关于加权网络聚类系数的三种定义具有如下特性:
3.6 度分布
3.6.1 度分布的概念
前面介绍过的节点的度的概念。在确定了网络中各个节点的度值之后,就可以进一步得到有关整个网络的一些性质。 首先,我们可以很容易计算出网络中所有节点的度的平均值,即网络节点的平均度(k)。
给定两个节点数相同的网络,它们的平均度相同也就等价于它们的总边数相同。
我们还可以把网络中节点的度按从小到大排序,从而统计得到度为h的节点占整个网络节点数的比例p
从概率统计的角度看,p也可以视为网络中一个随机选择的节点的度为h的概率,这就是度分布( Degree distribution)的概念。 无向网络的度分布P(k)定义为网络中一个随机选择的节点的度为k的概率。 有向网络：
出度分布(Out-degree distribution)P(k)定义为网络中随机选取的一个节点的出度为k的概率;入度分布( In-degree distribution)P(k)定义为网络中随机选取的一个节点的入度为k的概率。
图3-18给出了由7个节点组成的有向网络及其对应的人度分布和出度分布。
3.6.2 从钟形曲线到长尾分布
长尾分布( Long tail distribution ) ,如图3-21所示。长尾分布意味着大部分个体的取值都比较小,但是会有少数个体的取值非常大。以财富分布为例,尽管大部分人的个人财富都比较少(例如,不超过20万美元),但是也存在不少拥有至少100万美元财富的人,也存在相当数量拥有至少1 000万美元财富的人,还存在极少数拥有数亿财富的人。这一现象是钟形曲线无法描述的。 与钟形分布存在一个明显的特征标度不同,长尾分布往往不存在单一的特征标度,因此也称为无标度分布( Scale-free distribution)。
如果一个实际网络的度分布曲线近似具有钟形形状,其形状在远离峰值(k处呈指数下降。这意味着我们几乎可以肯定地认为网络中所有节点的度都与网络的平均度(k)相差不大。换句话说,网络中不存在一个具有比平均度(K)大得太多的度值的节点。因此,这类网络也称为均匀网络或匀质网络 然而,大量实证研究表明,许多实际网络的度分布曲线都具有长尾的形状。
3.7 幂律分布
3.7.1 幂律度分布及其校验
人们发现很多实际网络的度分布并不服从具有均匀特征的泊松分布,而是可以较好地用如下形式的幂律分布来表示:
介绍以下Pareto分布和Zipf定律
1. 双对数坐标系中的直线
2. 累计度分布
即使我们说网络的度分布在某段范围内服从幂律,实际情形往往会在其中的一些度值处(特别是尾部的一些地方)有明显的类似于噪声扰动的偏差。一种常见的光滑化的处理方法是绘制累积度分布(Cumulative degree distribution )P,它表示的是度不小于k的节点在整个网络中所占的比例,也就是网络中随机选取的一个节点的度不小于k的概率,即有
3.7.2 幂律分布的性质
1. 无标度的性质
2. 归一化
3. 矩的性质
度分布的m( m≥1)阶矩为
拓展：均匀与非均匀、幂律与无标度