网络基本拓扑性质

长河马俊强

1.割点与桥

割点：去除某个顶点使得图从连通变为不连通，那么称该点为割点(cut-vertex)；
桥：去除某条边使得一个图从连通变为不连通，那么该边成为桥(bridge)；
2.连通片

连通片(Giant component)：连通片包含网络相当比例的节点。
3.有向图中的蝴蝶结结构

有向图中的弱连通巨片：许多有向网络中往往有一个包含了网络中相当部分节点的很大的弱连通片，被称为弱连通巨片(Giant weakly connected component, GWCC)。弱连通巨片往往具有蝴蝶结结构(Bow-tie structure)。


蝴蝶结结构包含4个部分：
(1)强连通核(strongly connected core,SCC)：也称强连通巨片(giant strongly 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的有向路径。
(5)管子(Tube)：从挂在IN上的卷须节点到挂在Out上的卷须节点的不经过SCC的有向路径，这样串在一起的卷须节点称为管子。
4.度与平均度

无向网络中节点i的度ki表示与节点i直接相连的边的数目。
网络中所有节点的度的平均值称为网络的平均度<k>。
<k>=2M/N
5.出度与入度

有向图中节点的度包括节点的出度(out-degree)和入度(in-degree)。节点i的出度是指从节点i指向其他节点的边的数目，节点i的入度是指从其他节点指向节点i的边的数目。
单个节点的出度和入度可能不相同，但是这个网络的平均出度和入度是相同的，平均出度<k_out>=平均入度<k_in>=M/N。
出强度、入强度
6.网络的稀疏性与稠密化

网络的密度(Density)：定义为网络中实际存在的边数M与最大可能的边数之比。
对于无向图，密度公式如式(6.1)所示。对于有向网络去掉分母的1/2即可。


问题：随着时间的演化，网络是变得越来越稀疏还是越来越稠密？
平均度<k>是用来衡量网络稀疏性或稠密性的合理指标。
平均度和网络密度的关系如式(6.2)所示。


将时刻t时网络中的节点数和边数分别记为N(t)和M(t)。如果边数和点数呈线性关系，那么<k>为常数；如果M~N2，那么网络将会演化为一个非常复杂的网络。
研究表明，很多网络实际关系服从下列超线性关系，也称稠密化幂律，如式(6.3)所示。两边取对数可以得到式(6.4)。


式(6.3)表明，网络会随着时间的演化而越来越稠密，另一方面，与稠密的全耦合网络相比，实际网络依然是稀疏的。
式(6.4)表明双对数线性关系。
7.平均路径与直径

7.1无权无向图情形

7.1.1平均路径长度
最短路径：节点i和节点j之间的最短距离又称为测地路径(Geodesic path)，是指连接这两个节点的边数最少的路径。
节点i和节点j之间的距离定义为连接这两个节点的最短路径上的边的数目，也称为两个节点之间的测地距离(Geodesic distance)或者跳跃距离(Hop distance)。
网络的平均路径长度定义为任意两个节点之间的距离的平均值，如式(7.1)所示。


在实际情况中，如果无权无向图是不连通的，也即存在没有连边的节点对，其路径趋于正无穷，导致根据式(7.1)计算出的平均路径长度趋于无穷，不能收敛。
为了解决这种问题，提出了两种解决方案：
(1)把网络平均路径长度定义为存在连通路径的节点对之间的距离的平均值(这种方法只适用于存在一个包含相当部分节点的连通巨片的网络较为合适)；
(2)定义简谐距离(Harmonic mean)的概念，如式(7.2)所示


按照式(7.2)，当两点之间距离为无穷时，其倒数为0，由此可得平均路径长度总是有限值。其中GE定量反映了两个节点之间发送信息的平均效率，因此也称为全局效率(Global Efficiency)。
7.1.2网络直径
直径：网络中任意两个节点之间距离的最大值称为网络的直径(diameter)，如式(7.3)所示。


实际中的网络并不是连通的，而是存在一个连通巨片，所以在实际网络中，网络直径是指任意两个存在有限距离的节点之间距离的最大值。
进一步地，我们可能更关心的是网络中绝大部分用户对之间的距离；
用f(d)表示网络中距离为d的连通节点对的数量占整个网络中连通节点对数量的比例；
用g(d)表示网络中距离不超过d的节点对数量占整个网络中连通节点对数量的比例；
一般地，如果整数D满足式(7.4)，那么称D为网络的有效直径(Effective diameter)。


对任一实数r，假设d≤r<d+1，通过线性插值的方式定义g(r)如式(7.5)所示。


如果实数G满足g(D)=0.9，称D为网络的有效直径。
直径收缩(shrinking diameters)：许多实际网络的直径和有效直径都呈越来越小的趋势。
对于有向图或者加权图的情形。
8.聚类系数

8.1无权无向图情形

(1)聚类系数定义
聚类系数(Clustering coefficient)：定量刻画节点的邻居也互为邻居的概率，数学表达式定义如式(8.1)所示。


Ei表示节点i的ki个邻居节点之间实际存在的边数。
(2)几何定义
节点i的聚类系数的几何意义如式(8.2)所示。式(8.1)中Ei表示节点i的邻居中存在的边数，每存在一条边就意味着该边的两个节点与节点i构成一个三角形。节点i的邻居中任意两个节点如果不存在边，那么它们与节点i构成一个连通三元组。


一个网络的聚类系数C定义为网络中所有节点的聚类系数的平均值，如式(8.3)所示，显然有0≤C≤1。


(3)网络聚类系数的社会学定义
用网络中三角形的相对数量来刻画网络的聚类特性，也称横截性(Transitivity)，定义式如(8.4)所示。


公式中的因子(3)是由于每个三角形对应于3个不同的连通三元组，它们分别以三角形的三个顶点为中心。
8.2加权网络情形

用到的时候可以参考具体的论文，这里只做了简单归纳和总结。
给定一个加权网络G及其邻接矩阵A=(aij)和非负的权值矩阵W=(wij)，那么图G的聚类系数可以定义为式(8.5)。


对权值矩阵W应有如下限制：
(1)当节点i、j、k不构成三角形时，权值可取任意值，这里可取0；
(2)在无权网络中，式(8.5)即可退化为式(8.1)；
(3)权值的取值范围是[0,1]，


总小于Ci。
尽管有上述条件，权值wijk取法也不是唯一的，下面介绍两种取法：
取法1：取为节点i与它的两个相邻节点j和k之间两条边的权值的归一化平均值，如式(8.6)所示，代入到式(8.5)中可得聚类系数公式，如式(8.8)所示。


取法2：把wijk取为节点i和它的两个邻节点j和k组成的三角形的三条边的归一化均值的几何平均，如式(8.9)所示，因此聚类系数的另一个定义如式(8.11)所示。


9.度分布

度分布(Degree Distribution)：pk网络中一个随机选择的节点的度为k的概率，这就是度分布的概念。
有向图还分为出度分布和入度分布。
泊松分布满足式(9.1)，当λ（λ>0）增大时，分布的形状迅速接近正态曲线，常见的离散型概率分布P(k)有超几何分布、二项分布和泊松分布，它们在一定条件下都可以近似看成是正态分布的离散化形式，并且概率分布图都具有钟形形状。


服从钟形分布的随机变量具有一个明显的特征标度——钟形曲线的峰值，即随机变量的均值。
与钟形分布存在一个明显的特征标度不同，长尾分布往往不存在单一的特征标度，因此也被称为无标度分布(scale-free distribution)。若网络中不存在一个具有比平均度<k>大得太多的度值的节点。这类网络也称为均匀网络或匀质网络(Homogeneous network)。幂律分布是唯一一种具有无标度特性的长尾分布。
10.幂律分布

累积度分布：度不小于k的概率，如式(10.1)所示。也有些研究把1-Pk称为累积度分布。


如果一个网络的度分布为幂律分布，那么累积度分布函数近似复合幂指数为γ-1的幂律。（k值较大时，幂律函数变化较为缓慢）。


幂律分布函数是唯一满足无标度条件的概率分布函数。
归一化：
幂函数Pk=Ck-γ要成为概率分布必须要满足如下基本条件：


此外，度值k不能为0，否则p0无穷大。因此，我们不妨假设幂律分布是当k≥kmin>0时才成立，于是有


从而得到C的值


其中，


称为广义ζ函数，ζ(γ，1)（定义为ζ(γ)）称为标准黎曼函数。
m阶矩
度分布的m阶矩表示为


当m=1时，一阶矩即为网络的平均度。如果网络在k≥kmin时度分布具有幂律形式pk=Ck-γ，那么可以把k阶矩写为


再用积分近似求和


幂律分布 p_{k}=Ck^{-\gamma} 存在有限的m阶矩的充要条件为γ>m+1。