复杂网络的基础知识

《复杂网络的基础知识》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章复杂网络的基础知识第二章复杂网络的基础知识2.1网络的概念所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirectednetworks），否则为有向网络（directednetworks）。如果给每条边都赋予相应的权值，那么该网络就为加权网络（weightednetworks），否则为无权网络（unweightednetworks），如图2-1所示。图2-1网络类型示例(a)无权无向网络(b)加权网络(c)无权有向网络如果节点按照确定的规则连边，所得到的网络就称

2、为“规则网络”（regularnetworks），如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（randomnetworks）。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complexnetworks）。图2-2规则网络示例(a)一维有限规则网络(b)二维无限规则网络16第二章复杂网络的基础知识2.2复杂网络的基本特征量描述复杂网络的基本特征量主要有：平均路径长度（averagepathlength）、簇系数（clusteringefficient）、度分布（degreedistribution）、介数（b

3、etweenness）等，下面介绍它们的定义。2.2.1平均路径长度（averagepathlength）定义网络中任何两个节点i和j之间的距离lij为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径（diameter）为网络中任意两个节点之间距离的最大值。即（2-1）定义网络的平均路径长度L为网络中所有节点对之间距离的平均值。即（2-2）其中N为网络节点数，不考虑节点自身的距离。网络的平均路径长度L又称为特征路径长度（characteristicpathlength）。网络的平均路径长度L和直径D主要用来衡量网络的传输效率。2.2.2簇系数（cluster

4、ingefficient）假设网络中的一个节点i有ki条边将它与其它节点相连，这ki个节点称为节点i的邻居节点，在这ki个邻居节点之间最多可能有ki(ki-1)/2条边。节点i的ki个邻居节点之间实际存在的边数Ni和最多可能有的边数ki(ki-1)/2之比就定义为节点i的簇系数，记为Ci。即(2-3)整个网络的聚类系数定义为网络中所有节点i的聚类系数Ci的平均值，16第二章复杂网络的基础知识记为C。即（2-4）显然，0≤C≤1之间。当C=0时，说明网络中所有节点均为孤立节点，即没有任何连边。当C=1时，说明网络中任意两个节点都直接相连，即网络是全局耦合网络。2.2.3度分布（deg

5、reedistribution）网络中某个节点i的度ki定义为与该节点相连接的其它节点的数目，也就是该节点的邻居数。通常情况下，网络中不同节点的度并不相同，所有节点i的度ki的的平均值称为网络的（节点）平均度，记为。即（2-5）网络中节点的分布情况一般用度分布函数P(k)来描述。度分布函数P(k)表示在网络中任意选取一节点，该节点的度恰好为k的概率。即（2-6）通常，一个节点的度越大，意味着这个节点属于网络中的关键节点，在某种意义上也越“重要”。2.2.4介数（betweenness）节点i的介数定义为网络中所有的最短路径中，经过节点i的数量。用Bi表示。即（2-7）式中gm

6、n为节点m与节点n之间的最短路径数，gmin为节点m与节点n16第二章复杂网络的基础知识之间经过节点i的最短路径数。节点的介数反映了该节点在网络中的影响力。描述网络结构的特征量还有很多，这里就不一一介绍，在使用到它们的地方再给出详细的说明。2.3复杂网络的基本模型人们在对不同领域内的大量实际网络进行广泛的实证研究后发现：真实网络系统往往表现出小世界特性、无标度特性和高聚集特性。为了解释这些现象，人们构造了各种各样的网络模型，以便从理论上揭示网络行为与网络结构之间的关系，进而考虑改善网络的行为。下面介绍几类基本的网络模型。2.3.1规则网络（regularnetwork）常见的规则网

7、络有三种：全局耦合网络（globallycouplednetwork）、最近邻耦合网络（nearest-neighborcouplednetwork）和星型网络模型（starcouplednetwork），如图2-3所示。图2-3三种典型的规则网络(a)全局耦合网络(b)最近邻耦合网络(c)星型网络图2-3（a）所示为一个含有N个节点的全局耦合网络。网络中共有N(N-1)/2条边，其平均路径长度L=1（最小），簇系数C=1（最大）。度分布P(k)为以N-1为中心的δ函