第二章  复杂网络的基础知识
2.1 网络的概念
所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirected networks），否则为有向网络（directed networks）。如果给每条边都赋予相应的权值，那么该网络就为加权网络（weighted networks），否则为无权网络（unweighted networks），如图2-1所示。
图2-1  网络类型示例
(a) 无权无向网络    (b) 加权网络    (c) 无权有向网络
如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regular networks），如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（random networks）。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complex networks）。
图2-2  规则网络示例
(a) 一维有限规则网络    (b) 二维无限规则网络
2.2 复杂网络的基本特征量
描述复杂网络的基本特征量主要有：平均路径长度（average path length）、簇系数（clustering efficient）、度分布（degree distribution）、介数（betweenness）等，下面介
绍它们的定义。
2.2.1 平均路径长度（average path length）
定义网络中任何两个节点i和j之间的距离lij为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径（diameter）为网络中任意两个节点之间距离的最大值。即
                      （2-1）
定义网络的平均路径长度L为网络中所有节点对之间距离的平均值。即
                      （2-2）
其中N为网络节点数，不考虑节点自身的距离。网络的平均路径长度L又称为特征路径长度（characteristic path length）。
网络的平均路径长度L和直径D主要用来衡量网络的传输效率。
2.2.2 簇系数（clustering efficient）
假设网络中的一个节点i有ki条边将它与其它节点相连，这ki个节点称为节点i的邻居节点，在这ki个邻居节点之间最多可能有ki(ki-1)/2条边。节点i的ki个邻居节点之间实际存在的边数Ni和最多可能有的边数ki(ki-1)/2之比就定义为节点i的簇系数，记为正则化网络Ci。即
                          (2-3)
整个网络的聚类系数定义为网络中所有节点i的聚类系数Ci的平均值，记为C。即
                      （2-4）
显然，0 ≤ C ≤ 1之间。当C=0时，说明网络中所有节点均为孤立节点，即没有任何连边。当C=1时，说明网络中任意两个节点都直接相连，即网络是全局耦合网络。
2.2.3 度分布（degree distribution）
网络中某个节点i的度ki定义为与该节点相连接的其它节点的数目，也就是该节点的邻居数。通常情况下，网络中不同节点的度并不相同，所有节点i的度ki的的平均值称为网络的（节点）平均度，记为<k>。即
                      （2-5）
网络中节点的分布情况一般用度分布函数P(k)来描述。度分布函数P(k)表示在网络中任意选取一节点，该节点的度恰好为k的概率。即
                （2-6）
通常，一个节点的度越大，意味着这个节点属于网络中的关键节点，在某种意义上也越“重要”。
2.2.4 介数（betweenness）
节点i的介数定义为网络中所有的最短路径中，经过节点i的数量。用Bi表示。即

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。