复杂网络的聚类特性与幂律分布

2023-07-02 理论教育版权反馈

【摘要】：聚类系数节点i的邻居节点之间有可能互为邻居，这被称为网络的聚类特性。复杂网络的这种幂律分布特点成了它的致命弱点。研究表明，规则网络具有大的聚类系数和大的平均距离，随机网络具有小的聚类系数和小的平均距离。图3-4无标度网络

1）复杂网络简介

无论在社会科学、生命科学还是信息科学中，都存在着拥有十分复杂的拓扑结构特征的网络结构。这种网络结构的形式既不是完全规则，也不是完全随机的，例如在度分布中出现肥尾现象、高集聚系数、边与边之间的相称性或非相称性，社团结构与分级结构（hierarchy structure）等。在有向图网络中，还会出现相互性，三角显著性等其他方面的特征。然而，复杂网络的概念出现以前的数学网络模型并没有具备这样的特性。目前复杂网络理论的主要研究内容：发现、建模、分析、控制。

2）复杂网络统计特征

一个具体网络可抽象为一个由节点集以V（G）和边集E（G）组成的图G（V，E），节点数记为N，边数记为L。E（G）中每条边都有以V（G）中一对节点与之相对应。如果任意节点对（i，j）与（j，i）对应同一条边，则该网络称为无向网络，否则称为有向网络。如果给每条边都赋予相应的权值，那么该网络就称为加权网络。从网络统计特征来看，事实上Watts和Strogatz提出小世界网络的出发点就是想建立一个既类似于规则网络的具有较大聚类系数，又具有类似于随机图的较小的平均路径长度的网络模型；而Barabasi和Albert提出的无尺度网络模型则是基于许多实际网络的度分布具有幂律特点而建立的，这种幂律分布现象在物理学的一些系统和过程中已经研究了很长时间。此外，网络效率和鲁棒性也是衡量网络性能的重要指标。下面简单介绍一下各个指标的意义。

（1）度分布

网络中节点i的度k；被定义为与该节点连接的其他节点的数目，因此一个节点的度越大就意味着这个节点就越重要。网络的平均度定义为网络中所有节点i的度k；的平均值，记为k。网络中节点的度的分布情况可用分布函数p（k）来描述。p（k）为网络中度为k的顶点占所有顶点数的比值，也就是随机选取度为k的顶点的概率。

（2）平均路径长度

网络中连接这两个节点的最短路径包含的边数定义为两个节点i，j之间的距离dij。网络中任意两个节点之间的距离的最大值被定义为网络的直径D。网络的平均路径长度L定义为任意两个节点之间的距离的平均值。

（3）聚类系数

节点i的邻居节点之间有可能互为邻居，这被称为网络的聚类特性。设网络中的一个节点i有ki条边将它和其他节点相连，这ki个节点就称为节点i的邻居，它们之间最多可能有ki（ki-1）/2条边，而这ki个节点之间实际存在的边数式和总的可能存在边数ki（ki-1）/2之比就定义为节点i的聚类系数Ci。

pagenumber_ebook=67,pagenumber_book=58

（4）网络的效率

复杂网络的效率研究的是信息在网络上传播的有效性，可分为全局效率和局部效率，分别用Eglobal和Elocal表示。为了更好地且不失一般性地理解它们，以任意一个加权的网络G（V，E）为例对其进行分析。这样的加权网络需要用两个矩阵来描述：邻接矩阵{ai j}和描述真实距离的矩阵{lij}。其中aij与无权网络的定义一样，lij是两点之间的空间距离，例如lij是交通网络中两个地点之间的物理距离，在Internet网络中也可看做因特网上两个路由器之间交换信息包所花费的时间等。当然在特殊的无权网络中，满足lij＝1，i≠j。节点i至J间的最短路径长度dij是在图中从节点i至j的所有可能的路径中物理距离的和最短的路径。因此，矩阵{dij}是通过计算包含在矩阵{aij}和矩阵{lij}中的信息得出的。

（5）网络的鲁棒性

鲁棒性是复杂网络很重要的特征，是指把网络中的一些节点去掉后，看这个网络是否还是一个完整的网络。互联网的前身是由具有几个节点的网络演变而来，美国国防部当时是希望这个网络在受到攻击时，仍然能够保持通信的畅通。对于现在规模巨大的互联网的鲁棒性的研究开始于Barabasi等的研究工作。他们研究了均匀分布网络和无标度非均匀网络（包括互联网和万维网），发现这两种网络在网络鲁棒性方面呈现出很大的差异。尽管无标度网络具有很强的鲁棒性，但在遭受恶意攻击时性能急剧下降（这种特性称为脆弱性）。其研究指出，去掉1%的度值大的节点，网络的性能将下降一半；去掉4%的节点，网络将不能保证任意节点的连通性。在这样的网络中，如果度值大的节点受到恶意攻击，比如互联网中重要的服务器或网关等，整个网络很快就会陷入瘫痪状态。复杂网络的这种幂律分布特点成了它的致命弱点。Crucitti等研究了通信网络的抗攻击能力，得到了与上述结果一致的结论。

3）复杂网络的重要模型

（1）小世界网络

网络中，两点间的距离被定义为连接两点的最短路所包含的边的数目，把所有节点对的距离求平均，就得到了网络的平均距离，另外聚类系数则专用来衡量网络节点聚类的情况。比如在朋友关系网中，你朋友的朋友很可能也是你的朋友；你的两个朋友很可能彼此也是朋友。聚类系数就是用来度量网络的这种性质的。研究表明，规则网络具有大的聚类系数和大的平均距离，随机网络具有小的聚类系数和小的平均距离。经过统计分析发现，现实世界中的很多网络不同于规则网络和随机网络，而是具有大的聚类系数和小的平均距离。具有这种特征的网络就是小世界网络。

pagenumber_ebook=68,pagenumber_book=59

图3-3　小世界网络

（2）无标度模型

随着大量数据的产生和计算机的应用，科学家发现在现实世界里真实的网络表现出一种特别的属性：少数节点的连接数远远高于平均的节点连接数。进一步分析后发现，大量真实网络的节点度均服从幂率分布。节点度服从幂律分布是指某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。由于幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被看做其节点度的一个特征标度。在此意义上，把节点度服从幂律分布的网络称为无标度网络（Scale-free Networks），并称此幂律分布具有无标度特性。

pagenumber_ebook=69,pagenumber_book=60

图3-4　无标度网络

复杂网络的聚类特性与幂律分布

相关推荐