复杂网络基础理论第二章.ppt

《复杂网络基础理论第二章.ppt》由会员分享，可在线阅读，更多相关《复杂网络基础理论第二章.ppt（88页珍藏版）》请在三一办公上搜索。

1、复杂网络基础理论,第二章 网络拓扑结构与静态特征,第二章 网络拓扑结构与静态特征,2.1 引言2.2 网络的基本静态几何特征2.3 无向网络的静态特征2.4 有向网络的静态特征2.5 加权网络的静态特征2.6 网络的其他静态特征2.7 复杂网络分析软件,2,2.1 引言,与图论的研究有所不同，复杂网络的研究更侧重于从各种实际网络的现象之上抽象出一般的网络几何量，并用这些一般性质指导更多实际网络的研究，进而通过讨论实际网络上的具体现象发展网络模型的一般方法，最后讨论网络本身的形成机制。统计物理学在模型研究、演化机制与结构稳定性方面的丰富的研究经验是统计物理学在复杂网络研究领域得到广泛应用的原因；

2、而图论与社会网络分析提供的网络静态几何量及其分析方法是复杂网络研究的基础。,3,2.1 引言,静态特征指给定网络的微观量的统计分布或宏观统计平均值。在本章中我们将对网络的各种静态特征做一小结。由于有向网络与加权网络有其特有的特征量，我们将分开讨论无向、有向与加权网络。,4,返回 目录,2.2 网络的基本静态几何特征,2.2.1 平均距离2.2.2 集聚系数2.2.3 度分布2.2.4 实际网络的统计特征,5,2.2.1 平均距离,1.网络的直径与平均距离 网络中的两节点vi和vj之间经历边数最少的一条简单路径（经历的边各不相同），称为测地线。测地线的边数dij称为两节点vi和vj之间的距离（或

3、叫测地线距离）。1dij称为节点vi和vj之间的效率，记为ij。通常效率用来度量节点间的信息传递速度。当vi和vj之间没有路径连通时，dij，而ij0，所以效率更适合度量非全通网络。网络的直径D定义为所有距离dij中的最大值,6,2.2.1 平均距离,平均距离（特征路径长度）L定义为所有节点对之间距离的平均值，它描述了网络中节点间的平均分离程度，即网络有多小，计算公式为 对于无向简单图来说，dijdji且dii0，则上式可简化为 很多实际网络虽然节点数巨大，但平均距离却小得惊人，这就是所谓的小世界效应。,7,2.2.1 平均距离,2.距离与邻接矩阵的关系 定义对于无权简单图来说，当l1时，。容

4、易证明无权简单图邻接矩阵A的l次幂Al的元素 表示节点vi和vj之间通过l条边连接的路径数。当l2时，容易推出式中，U表示单位指示函数，即当x0，U（x）1；否则U（x）0。当ij时，ij1；否则ij0。,8,2.2.1 平均距离,容易用数学归纳法证明据此，若D为网络直径，则两节点vi和vj之间的距离dij可以表示为,9,2.2.2 集聚系数,首先来看节点的集聚系数定义。假设节点vi与ki个节点直接连接，那么对于无向网络来说，这ki个节点间可能存在的最大边数为ki（ki1）2，而实际存在的边数为Mi，由此我们定义Ci2Miki（ki1）为节点vi的集聚系数。对于有向网络来说，这ki个节点间可能

5、存在的最大弧数为ki（ki1），此时vi的集聚系数CiMiki（ki1）。将该集聚系数对整个网络作平均，可得网络的平均集聚系数为,10,2.2.2 集聚系数,显然，0C1。当C0，所有节点都是孤立节点，没有边连接。当C1时，网络为所有节点两两之间都有边连接的完全图。对于完全随机网络来说，当节点数很大时，CO（1N）。而许多大规模的实际网络的集聚系数通常远小于1而大于O（1N)。对于社会网络来说，通常随着N，集聚系数CO（1），即趋向一个非零常数。节点vi的集聚系数也可定义为CiNiNi。式中Ni代表与节点vi相连的“三角形”数目，数值上就等于Mi；Ni代表与节点vi相连的“三元组”数目，即节点

6、vi与其它两个节点都有连接，即“至少与其他两个分别认识”，数值上就等于ki（ki1）2。,11,2.2.2 集聚系数,如何根据无向无权简单图的邻接矩阵A来求节点vi的集聚系数Ci？显然，邻接矩阵二次幂A2的对角元素 表示的是与节点vi相连的边数，也就是节点vi的度ki。而邻接矩阵三次幂A3的对角元素（aijajlali）（jl）表示的是从节点vi出发经过三条边回到节点vi的路径数，也就是与节点vi相连的三角形数的两倍（正向走和反向走）。因此，由集聚系数的定义可知,12,2.2.2 集聚系数,【例2.1】计算下面简单网络的直径、平均距离和各节点的集聚系数。解：首先计算出所有节点对的距离：d121

7、；d131；d142；d151；d162；d231；d241；d252；d262；d342；d352；d361；d453；d461；d563。由此可得直径和平均距离为,13,2.2.2 集聚系数,下面以节点v1的集聚系数计算为例：采用第一种定义可知，节点v1与3个节点直接连接，而这3个节点之间可能存在的最大边数为3（31）2，而实际存在的边数为1，由此可得C123（31）13。若采用第二种定义可知：与相连的三角形数为N1，而与v1相连的三元组数为N13，故C113。也可以利用式 计算，因为邻接矩阵A的前三次幂为,14,2.2.2 集聚系数,故 2，3，从而同理可得其他各节点的集聚系数为C213

8、；C313；C40；C50；C60由此很容易算出该网络的集聚系数,15,2.2.3 度分布,1.节点的度 在网络中，节点vi的邻边数ki称为该节点vi的度。对网络中所有节点的度求平均，可得到网络的平均度k 无向无权图邻接矩阵A的二次幂A2的对角元素 就是节点vi的邻边数，即。实际上，无向无权图邻接矩阵A的第i行或第i列元素之和也是度。从而无向无权网络的平均度就是A2对角线元素之和除以节点数，即ktr（A2）N。式中，tr（A2）表示矩阵A2的迹，即对角线元素之和。,16,2.2.3 度分布,2.度分布 大多数实际网络中的节点的度是满足一定的概率分布的。定义P（k）为网络中度为k的节点在整个网络

9、中所占的比率。规则网络：由于每个节点具有相同的度，所以其度分布集中在一个单一尖峰上，是一种Delta分布。完全随机网络：度分布具有Poisson分布的形式，每一条边的出现概率是相等的，大多数节点的度是基本相同的，并接近于网络平均度k，远离峰值k，度分布则按指数形式急剧下降。把这类网络称为均匀网络。无标度网络：具有幂指数形式的度分布：P（k）k。所谓无标度是指一个概率分布函数F（x）对于,17,2.2.3 度分布,任意给定常数a存在常数b使得F（x）满足F（ax）bF（x）。幂律分布是唯一满足无标度条件的概率分布函数。许多实际大规模无标度网络，其幂指数通常为23，绝大多数节点的度相对很低，也存在

10、少量度值相对很高的节点（称为hub），把这类网络称为非均匀网络。指数度分布网络：P（k）ek/，式中0为一常数。,18,2.2.3 度分布,3.累积度分布 可以用累积度分布函数来描述度的分布情况，它与度分布的关系为它表示度不小于k的节点的概率分布。若度分布为幂律分布，即P（k）k，则相应的累积度分布函数符合幂指数为1的幂律分布 若度分布为指数分布，即P（k）ek/，则相应的累积度分布函数符合同指数的指数分布,19,2.2.4 实际网络的统计特征,20,返回 目录,2.3 无向网络的静态特征,2.3.1 联合度分布和度度相关性2.3.2 集聚系数分布和聚度相关性2.3.3 介数和核度2.3.4

11、中心性2.3.5 网络密度2.3.6 连通集团（子图）及其规模分布,21,2.3.1 联合度分布和度度相关性,1.联合度分布 度分布满足 平均度与度分布具有关系式 联合度分布定义为从无向网络中随机选择一条边，该边的两个节点的度值分别为k1和k2的概率，即式中，M（k1，k2）为度值为k1的节点和度值为k2的节点相连的总边数，M为网络总边数。从联合度分布可以得出度分布式中，1（kk2）；0（kk2）。,22,2.3.1 联合度分布和度度相关性,联合节点度分布所包含的拓扑信息最多，节点度分布次之，平均节点度最少。2.基于最近邻平均度值的度度相关性 度度相关性描述了网络中度大的节点和度小的节点之间的

12、关系。若度大的节点倾向于和度大的节点连接，则网络是度度正相关的；反之，若度大的节点倾向于和度小的节点连接，则网络是度度负相关的。节点vi的最近邻平均度值定义为式中，ki表示节点vi的度值，aij为邻接矩阵元素。,23,2.3.1 联合度分布和度度相关性,所有度值为k的节点的最近邻平均度值的平均值knn（k）定义为式中，N为节点总数，P（k）为度分布函数。如果knn（k）是随着k上升的增函数，则说明度值大的节点倾向于和度值大的节点连接，网络具有正相关特性，称之为同配网络；反之网络具有负相关特性，称之为异配网络。3.基于Pearson相关系数的度度相关性 Newman利用边两端节点的度的Pears

13、on相关系数r来描述网络的度度相关性，具体定义为,24,2.3.1 联合度分布和度度相关性,式中，ki，kj分别表示边eij的两个节点vi，vj的度，M表示网络的总边数。容易证明度度相关系数r的范围为：0|r|1。当r0时，网络是正相关的；当r0时，网络是不相关的。,25,2.3.2 集聚系数分布和聚度相关性,1.集聚系数分布 集聚系数分布函数P（C）表示从网络中任选一节点，其集聚系数值为C的概率式中，（x）为单位冲激函数。2.聚度相关性 局部集聚系数C（k）定义为度为k的节点的邻居之间存在的平均边数Mnn（k）与这些邻居之间存在的最大可能的边数的比值，即,26,2.3.2 集聚系数分布和聚度

14、相关性,全局集聚系数C则定义为式中，k2为度的二阶矩。显然，局部集聚系数C（k）与k的关系刻画了网络的聚度相关性。许多真实网络如好莱坞电影演员合作网络、语义网络中节点的聚度相关性存在近似的倒数关系C（k）k1。把这种倒数关系的聚度相关性称为层次性，把具有层次性的网络称为层次网络。,27,2.3.3 介数和核度,1.介数 要衡量一个节点的重要性，其度值当然可以作为一个衡量指标，但又不尽然，例如在社会网络中，有的节点的度虽然很小，但它可能是两个社团的中间联络人，如果去掉该节点，那么就会导致两个社团的联系中断，因此该节点在网络中起到极其重要的作用。对于这样的节点，需要定义另一种衡量指标，这就引出网络

15、的另一种重要的全局几何量介数。介数分为节点介数和边介数两种，反映了节点或边在整个网络中的作用和影响力。,28,2.3.3 介数和核度,节点的介数Bi定义为式中，Njl表示节点vj和vl之间的最短路径条数，Njl（i）表示节点vj和vl之间的最短路径经过节点vi的条数。边的介数Bij定义为式中，Nlm表示节点vl和vm之间的最短路径条数，Nlm（eij）表示节点vl和vm之间的最短路径经过边eij的条数。,29,2.3.3 介数和核度,2.介数分布和介度相关性 节点的介数与度之间有很强的相关性，而且不同类型的网络，其介数分布也大不一样。介度相关性可以用B（k）k表示，它定义为所有度为k的节点的介

16、数平均值随着k的变化关系。节点介数分布Pv（B）定义为网络中节点介数为B的节点数占网络节点总数的比例。边介数分布Pe（B）定义为网络中边介数为B的边数占网络总边数的比例。研究表明，节点的最大介数与网络的同步能力密切相关：节点的最大介数越大，网络的同步能力越弱。,30,2.3.3 介数和核度,3.核度 一个图的k核是指反复去掉度值小于k的节点及其连线后，所剩余的子图，该子图的节点数就是该核的大小。若一个节点属于k核，而不属于（k1）核，则此节点的核度为k。节点核度的最大值叫做网络的核度。节点的核度可以说明节点在核中的深度，核度的最大值自然就对应着网络结构中最中心的位置。k核解析可用来描述度分布所

17、不能描述的网络特征，揭示源于系统特殊结构的结构和层次性质。,31,2.3.3 介数和核度,【例2.2】计算下面网络的一些特性：（1）度分布及平均度；（2）联合度分布并验证 的正确性；（3）各节点的最近邻平均度值knn,i；（4）该网络是否是同配网络；（5）该网络是否是正相关网络；（6）分别求各节点和各连接边的介数；（7）求该网络的2核，3核及各自核度大小，并计算该网络的核度。,32,2.3.3 介数和核度,解：（1）该网络的度分布如下表所示。因此或（2）根据 容易得到联合度分布如下表所示。由此可以验证 的正确性，例如当k1时，该式左边P（1）=16，而右边为,33,2.3.3 介数和核度,（3

18、）利用 得v1v6的最近邻平均度值knn,i分别为：73、83、83、52、3、52。（4）利用 得度为1、2、3的节点的最近邻平均度值的平均值knn（k）分别为：3、52、239。由于随着k的增加knn（k）下降，所以该网络是异配网络。（5）Pearson相关系数因为r0，说明该网络为负相关。（6）由图可知各节点之间的最短路径分别为：v1e2v2；v1e3v3；v1e2v2e5v4；v1e1v5；v1e3v3e7v6；v2e4v3；v2e5v4；v2e2v1e1v5；v2e4v3e7v6；v2e5v4e6v6；v3e4v2e5v4；v3e7v6e6v4；v3e3v1e1v5；v3e7v6；v

19、4e5v2e2v1e1v5；v4e6v6；v5e1v1e3v3e7v6。,34,2.3.3 介数和核度,由此可得v1v6各节点的介数Bi为：4、2.5、2.5、0.5、0、0.5。同理可得e1e7各边的介数为：4、3、3、1、3、1、3。（7）该网络的2核，3核如下图所示，它们核的大小分别为5和3。节点v1v6的核度分别为3、3、3、2、1、2，所以网络的核度为3。,35,2.3.4 中心性,1.度中心性 度中心性分为节点度中心性和网络度中心性。前者指的是节点在其与之直接相连的邻居节点当中的中心程度，而后者则侧重节点在整个网络的中心程度，表征的是整个网络的集中或集权程度，即整个网络围绕一个节点

20、或一组节点来组织运行的程度。节点vi的度中心性CD（vi）定义为 在所有含N节点的网络中，假设网络Goptimal使得下式达到最大值式中，ui为网络Goptimal的各个节点，u max表示网络Goptimal中拥有最大度中心性的节点。,36,2.3.4 中心性,对于含N节点的某网络G，令vmax表示其拥有最大度中心性的节点，则网络G的度中心性CD定义为 当图Goptimal为星型网络时，H值达到最大，即 因此，网络G的度中心性CD可简化为,37,2.3.4 中心性,2.介数中心性 介数中心性分为节点介数中心性和网络介数中心性。节点vi的介数中心性CB（vi）定义为 与度中心性类似，可得HN1

21、（也是星型网络，中心节点的介数中心性为1，其它节点的介数中心性为0）。因此，网络G的介数中心性CB可简化为,38,2.3.4 中心性,3.接近度中心性 对于连通图来说，节点vi的接近度中心性CC（vi）定义为 与度中心性类似，可得H（N1）（N2）（2N3）（也是星型网络）。因此，连通网络G的接近度中心性CC可简化为 对于非连通图来说，上述定义需要做一定的修正，一个比较好的做法是分别计算各个连通分支的中心性，然后根据各连通分支的阶数进行加权。,39,2.3.4 中心性,4.特征向量中心性Axx 通常，上式的各个特征向量对应不同的特征值。在这里，一个额外的要求是特征向量的每个分量必须是正数。根据

22、PerronFrobenius定理，只有最大的特征值对应的特征向量才是中心性测度所需要的。求这个特征向量可采用幂迭代算法。在最后得到的特征向量中，第i个分量xi就是节点vi的特征向量中心性CE（vi）。,40,2.3.5 网络密度,网络密度指的是一个网络中各节点之间联络的紧密程度。网络G的网络密度d（G）定义为式中，M为网络中实际拥有的连接数，N为网络节点数。网络密度的取值范围为0，1，当网络内部完全连通时，网络密度为1，而实际网络的密度通常远小于1，实际网络中能够发现的最大密度值是0.5。不同规模网络的密度无法进行比较。为了解决这一问题，John Scott提出了“绝对密度”公式式中，D表示

23、网络直径，R表示半径，S表示根据直径算出的圆周长。,41,2.3.6 连通集团（子图）及其规模分布,1.连通、连通集团（子图）和连通分支（最大连通子图）连通集团（子图）就是指网络G中的一个子图，在这个子图内，任意两个节点之间都至少存在一条简单路径。对于非连通图G来说，肯定可以将其分解为两个或两个以上的连通分支。所谓连通分支就是最大连通子图，即该连通子图加入任何其它节点都将影响该子图的连通性。图G中的每个节点只能属于一个连通分支，边也一样。显然，连通图的连通分支数为1，而非连通图的连通分支数大于1。把网络的各连通分支中阶数最大的一个称为最大连通分支。,42,2.3.6 连通集团（子图）及其规模分

24、布,2.连通度 连通图G的连通程度通常叫做连通度。连通度有两种，一种是点连通度，一种是边连通度。通常一个图的连通度越好，它所代表的网络越稳定。点连通度定义为式中，V是图G的节点集合，S为V的真子集，（GS）表示从图G中删除点集S后得到的子图GS的连通分支数。这里GS是指删除S中每一个节点以及图G中与之关联的所有边。由此可见，点连通度就是使G不连通或成为平凡图所必须删除的最少节点个数。对于不连通图或平凡图，定义（G）0；若G为N阶完全图，（G）N1。,43,2.3.6 连通集团（子图）及其规模分布,边连通度定义为式中，E是图G的边集合，T为E的真子集，（GT）表示从图G中删除边集T后得到的子图G

25、T的连通分支数。这里GT是指删除T中每一条边，而G中所有节点全部保留下来。由此可见，边连通度就是使G不连通所必须删除的最少边数。对于不连通图或平凡图，定义（G）0；若G为N阶完全图，（G）N1。可以证明，同一个图的点连通度和边连通度满足（G）（G）。,44,2.3.6 连通集团（子图）及其规模分布,3.连通集团的规模分布 连通集团的规模分布反映了网络G中的各种规模的连通分支的数目分布情况。实证研究表明，对于大量的无标度网络，连通集团的规模也存在幂律分布。例如，科学家合作网的连通子图规模分布。,45,返回 目录,2.4 有向网络的静态特征,2.4.1 入度和出度及其分布2.4.2 度度相关性2.

26、4.3 平均距离和效率2.4.4 入集团和出集团的集聚程度2.4.5 介数和双向比2.4.6 中心性,46,2.4.1 入度和出度及其分布,1.入度与出度 由于与有向网络某个节点相关联的弧有指向节点的，也有背向节点向外的，因此除了可以统计与某个节点相关联的弧数，也就是度之外，有必要分开统计两个方向的弧数，分别称为节点的入度和出度。节点vi的入度、出度和有向图的邻接矩阵以及度的关系为,47,2.4.1 入度和出度及其分布,同平均度一样，也可以求平均入度kin和平均出度kout为2.入度分布和出度分布 入度分布和出度分布分别记为Pin（k）和Pout（k），分别表示网络中任意取出一个节点，其入度值

27、和出度值刚好为k的概率。入（出）度分布与平均入（出）度之间具有如下关系式,48,2.4.1 入度和出度及其分布,3.累积入度分布和累积出度分布 累积入（出）度分布与入（出）度分布的关系为 容易证明入（出）度幂律分布对应的累积分布也是幂律分布，入（出）度指数分布对应的累积分布也是同指数的指数分布。4.联合度分布 联合度分布有两种定义方式，第一种定义方式是基于弧的方式，第二种定义方式是基于节点的方式。,49,2.4.1 入度和出度及其分布,基于弧的方式：从网络中随机选择一条弧，该弧由入度和出度分别为（jin，jout）的节点连向入度和出度分别为（kin，kout）的节点的概率，即式中，M（jin，

28、jout；kin，kout）为由入度和出度分别为jin和jout的节点连向入度和出度分别为kin和kout的节点的弧数，M为网络总弧数。注意，联合概率Pe（jin，jout；kin，kout）不是对称的，即Pe（jin，jout；kin，kout）Pe（kin，kout；jin，jout）。若对上式按照（kin，kout）求和，就得到随机选取一条弧，该弧起点的度为（jin，jout）的概率,50,2.4.1 入度和出度及其分布,若对上式按照（jin，jout）求和，就得到随机选取一条弧，该弧终点的度为（kin，kout）的概率 基于节点的方式：从网络中随机选择一个节点，其入度值和出度值分别为k

29、in和kout的概率，即式中，N（kin，kout）为入度值和出度值分别为kin和kout的节点数，N为网络总节点数。Pv（kin，kout）和Pf（kin，kout）、Pt（kin，kout）具有如下关系式,51,2.4.2 度度相关性,度度相关性也有两种定义方式，即基于节点的方式和基于弧的方式。1.基于节点的入度出度相关性 可以定义节点的入度为kin的情况下其出度为kout的条件概率为 然后，可以定义基于节点的入度出度相关性为 更简便的定义为 如果kvv（kin）kin曲线的斜率小于0，则kin和kout负相关；斜率大于0，则kin和kout正相关；等于0，则kin和kout不相关。,52

30、,2.4.2 度度相关性,2.基于弧的度度相关性 任意选取一条弧，在弧的两端存在两个度值，起点的入度和出度，终点的入度和出度，所以存在四种相关性，分别是起点入度终点入度，起点出度终点入度，终点入度起点出度以及终点出度起点出度,分别记做kin-in（kin）kin，kout-in（kin）kin，kin-out（kout）kout，kout-out（kout）kout。这四种相关性可分别定义如下,53,2.4.3 平均距离和效率,由于有向网络里的弧是带有方向的，所以从节点vi到vj之间的距离dij和从节点vj到vi之间的距离dji是不同的。距离dij定义为从节点vi出发沿着同一方向到达节点vj所

31、要经历的弧的最少数目，而它的倒数1dij称为从节点vi到节点vj的效率，记为ij。有向连通简单网络的平均距离L定义为所有节点对之间距离的平均值，定义为 因为效率可以用来描述非连通网络，所以可以定义有向网络的效率LC为,54,2.4.4 入集团和出集团的集聚程度,对于某个节点vi来说，所有以该节点为终点的弧的起始节点及它们之间的连弧构成一个小集团，称之为入集团；而所有以该节点为起点的弧的终止节点及它们之间的连弧构成一个小集团，称之为出集团。由于节点vi的入度为kiin，则连向该节点的kiin个起始节点间可能存在的最大弧数为kiin（kiin1），而实际存在的弧数为Miin，由此定义为节点vi的入

32、集聚系数，然后将该集聚系数对整个网络作平均，即可得网络的入集团的集聚系数。,55,2.4.4 入集团和出集团的集聚程度,同理，定义为节点vi的出集聚系数，然后将该集聚系数对整个网络作平均，即可得网络的出集团的集聚系数。,56,2.4.4 入集团和出集团的集聚程度,【例2.3】针对下图所示网络分别计算：（1）写出该网络的邻接矩阵、入度分布及出度分布；（2）分别求出该网络的Pf（kin，kout）、Pt（kin，kout）和Pv（kin，kout）；（3）整个网络的入集团和出集团的集聚系数。,57,2.4.4 入集团和出集团的集聚程度,解：（1）该网络的邻接矩阵为 入度分布如下表所示 出度分布如下

33、表所示（2）联合概率分布Pe（jin，jout；kin，kout）如下表所示,58,2.4.4 入集团和出集团的集聚程度,由上表可得Pf（jin，jout），如下表所示 Pt（kin，kout）如下表所示 Pv（kin，kout）如下表所示,59,2.4.4 入集团和出集团的集聚程度,（3）以节点v5为例，其对应的入集团如下图所示，由此可计算出节点v5的入集团集聚系数同理可计算出每个节点的入集团的集聚系数为：0、0、0、12、16、0。而每个节点的出集团的集聚系数为：12、0、0、0、0、13。因此，可得网络的入集团和出集团集聚系数分别为19和536。,60,2.4.5 介数和双向比,1.介数

34、 节点的介数Bi定义为式中，Njl表示从节点vj到vl的最短路径条数，Njl（i）表示从节点vj到vl的最短路径经过节点vi的条数。边的介数Bij定义为式中，Nlm表示从节点vl到vm的最短路径条数，Nlm（eij）表示从节点vl到vm的最短路径经过边eij（方向相同）的条数。,61,2.4.5 介数和双向比,2.双向比 双向比，即两两节点间双向边的总数占网络所有边的比例。假设有向图中含有MB条双向边，则双向比就是：RBMBM。例如下图所示的有向图，其双向比为0.5。,62,2.4.6 中心性,1.入度中心性和出度中心性 节点vi的入度中心性CD_in（vi）定义为 令vmax表示网络G中拥有

35、最大入度中心性的节点，则网络G的入度中心性定义为 节点vi的出度中心性CD_out（vi）定义为 令vmax表示网络G中拥有最大出度中心性的节点，则网络G的出度中心性定义为,63,2.4.6 中心性,2.介数中心性 节点vi的介数中心性CB（vi）定义为 令vmax表示网络G中拥有最高介数中心性的节点，则网络G的介数中心性CB定义为,64,返回 目录,2.5 加权网络的静态特征,2.5.1 点权、单位权和权重分布差异性2.5.2 权度相关性和权权相关性2.5.3 距离分布和平均距离2.5.4 加权集聚系数2.5.5 介数分布和漏斗效应2.5.6 有向加权网络的最短路径问题,65,2.5.1 点

36、权、单位权和权重分布差异性,1.点权 节点vi的点权Si定义为式中，Ni表示节点vi的邻点集合，wij表示连接节点vi和节点vj的边的权重。对于无向加权网络，点权Si还可以用邻接矩阵元素表示为式中，aij为邻接矩阵元素（若节点vi与vj无连接则aij0，若有连接则aij1）。对于有向加权网络，可定义入权和出权。,66,2.5.1 点权、单位权和权重分布差异性,入权Siin为以节点vi为终点的所有弧的边权之和，而出权Siout为以节点vi为起点的所有弧的边权之和，即而点权满足2.单位权 单位权表示节点连接的平均权重，它定义为 对于有向加权网络，也可以分别定义单位入权和单位出权如下,67,2.5.

37、1 点权、单位权和权重分布差异性,3.权重分布的差异性 节点vi的权重分布差异性Yi表示与节点vi相连的边权分布的离散程度，定义为 对于无向加权网络，可以用邻接矩阵表示为 差异性与度有如下关系：如果与节点vi关联的边的权重值差别不大，则Yi1ki；如果权值相差较大，例如只有一条边的权重起主要作用，则Yi1。对于有向加权网络，也可以分别定义入权差异性和出权差异性，即,68,2.5.2 权度相关性和权权相关性,1.基于节点的权度相关性 基于节点的权度相关性指的是对于单个节点来说，其点权和其度之间的相关性。对于无向网络，就是S和k的关系，其定义为式中，N为节点总数，P（k）为度分布函数。当边权与网络

38、拓扑结构无关时，通常呈现Svv（k）wk的分布情况，其中w表示所有边权的平均值；当边权与网络拓扑结构有关时，通常呈现Svv（k）Ak的分布情况（要么指数1，要么常数A）。对于有向网络，除了S和k的关系，还有Sinkin，Sinkout，Soutkin，Soutkout四种相关性。,69,2.5.2 权度相关性和权权相关性,2.基于边的权度相关性 基于边的权度相关性类似于无向网络的度度相关性，它考察的是较大权重的边是倾向于与度值大的节点相连，还是倾向于与度值小的节点相连，还是根本没有关系。对于无向加权网络，类似knn,i，可定义节点的加权平均近邻度为式中，kj表示节点vj的度值，aij为邻接矩阵

39、元素。若所有节点满足kw_nn,iknn,i，则表明具有较大权重的边倾向于连接具有较大度值的点。若所有节点满足kw_nn,iknn,i，则表明具有较大权重的边倾向于连接具有较小度值的点。,70,2.5.2 权度相关性和权权相关性,可定义所有度为k的节点的加权平均近邻度的平均值kw_nn（k）为若曲线斜率大于0，表示具有正相关性；若曲线斜率小于0，表示具有负相关性；若曲线斜率为0，表示不相关。类似地，也可以研究有向网络基于弧的权度相关性。任意选取一条弧，在弧的两端各存在两个度值，所以存在四种相关性，加权平均近邻入度与入度、加权平均近邻出度与入度、加权平均近邻入度与出度、加权平均近邻出度与出度，分

40、别记做kw_in-in（kin）kin，kw_out-in（kin）kin，kw_in-out（kout）kout，kw_out-out（kout）kout。,71,2.5.2 权度相关性和权权相关性,3.权权相关性 权相关性有两类，一类是点权点权相关性，一类是单位权单位权相关性，定义方式差不多，这里以点权为例。对于无向加权网络，类似knn,i，可定义节点的加权平均近邻权为 于是所有点权为S的节点的加权平均近邻权的平均值Snn（S）为,72,2.5.2 权度相关性和权权相关性,类似地，也可以研究有向网络基于弧的权权相关性。任意选取一条弧，在弧的两端各存在两个权值，所以存在四种相关性，分别是起点

41、入权终点入权，起点出权终点入权，终点入权起点出权以及终点出权起点出权,分别记做Sin-in（Sin）Sin，Sout-in（Sin）Sin，Sin-out（Sout）Sout，Sout-out（Sout）Sout。,73,2.5.3 距离分布和平均距离,若边eij的权重wij表示相异权，则其长度dijwij；若wij表示相似权，则其长度dijwij。假设节点vi和vk通过两条权重分别为wij和wjk的边相连，则在相异权情况下，vi和vk之间的距离dikwijwjk；而在相似权情况下，vi和vk之间的距离dik1wij1wjk。加权网络中的最短路径是指在两点之间所有连通的路径中，相异权权重之和（

42、相似权权重倒数之和）最小的一条或几条路径。距离分布P（d）是指距离为d的节点对数占总节点对数的比重。无向连通简单加权网络的平均距离L定义为 有向连通简单加权网络的平均距离L定义为,74,2.5.4 加权集聚系数,Barrat定义式 Onnela定义式式中，表示归一化权重。Holme定义式,75,2.5.4 加权集聚系数,【例2.4】分别计算下图所示网络（设权值为相似权）的下述特性：（1）分别求出各节点的点权、单位权、权重差异性；（2）求出网络的基于节点的权度相关性Svv（k）；（3）根据集聚系数的Holme定义式，求出各节点的加权集聚系数。解：（1）节点v1v6的点权Si分别为：4、7、13、

43、9、11、8；单位权Ui分别为：2、73、133、3、114、83；权重差异性Yi分别为：58、37、57169、3581、31121、1332。,76,2.5.4 加权集聚系数,（2）该网络的度分布如下表所示 可得基于节点的权度相关性Svv（k）如下表所示（3）节点v1v6的加权集聚系数分别为：23、328、114、29115、19、2976。,77,2.5.5 介数分布和漏斗效应,介数是用来衡量通过网络中某节点或某条边的最短路径的数目。在科学家网络中，介数反映了在本领域内，某位科学家影响力的大小。某一节点的近邻节点介数分布的两极分化性质称为漏斗效应，也就是说只和本领域的1个或2个著名成员合

44、作就能够很容易与合作网络大部分成员建立最短路径，而所有这些短路径都将通过这几个著名成员。而全部节点的介数分布反映的是科学家影响力的层次。边的介数反映的是不同科学家之间的交流对学科发展影响力的不同。同时，利用边的介数也可以对科学家做聚类分析。,78,2.5.6 有向加权网络的最短路径问题,1.最短路径问题 算法具体形式包括：已知起始节点，求最短路径的问题。已知终止节点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。已知起点和终点，求两节点之间的最短路径。全局最短路径问题，即求图中所有的最短路径。2.Dijkstra算法3.B

45、ellman-Ford算法4.Floyd-Warshall算法,79,返回 目录,2.6 网络的其他静态特征,2.6.1 网络结构熵2.6.2 特征谱2.6.3 度秩函数2.6.4 富人俱乐部系数,80,2.6.1 网络结构熵,假设网络中节点vi的度为ki，则其重要度可定义为对于ki0的节点不作考虑，可以定义网络结构熵为当网络完全均匀，即Ii1N时，EmaxlnN。当网络最不均匀，即I112，Ii12（N1）（i1）时，Eminln4（N1）2。为了消除节点数目N对E的影响，可以对网络结构熵进行归一化，定义为网络标准结构熵。显然。,81,2.6.1 网络结构熵,网络结构熵与度分布的关系就如同随

46、机变量的数字特征与其概率分布函数的关系。两者是互为补充的，网络结构熵是由度分布确定的，而网络结构熵可以更加精确简洁地度量复杂网络的非同质性。熵的定义可以为我们衡量网络的连通性和研究网络中哪些节点是其中的核心节点提供度量标准，这样就能对我们选择保护哪些网络中的节点才能起到保护整个网络的作用给予有价值的指导。,82,2.6.2 特征谱,令对角阵D的对角元素分别是各节点的度，即diiki，则称矩阵LDA为网络G的Laplacian矩阵。特征谱，就是矩阵A或L特征值的集合，是图的所有特征值连同其重数构成的重集。网络的谱密度也叫做状态密度，它是特征值分布特性的表现形式。设简单无向网络G有N个节点，由于它

47、的邻接矩阵A是实对称矩阵，因此它有N个实特征值（重特征值按重数计算），记为j，j1，2，N。下面的描述假设12N。借助邻接矩阵的特征值，可以定义谱密度（）和其p阶矩Mp，即,83,2.6.2 特征谱,式中，（）是单位冲激函数。容易证明（）是一种谱密度，因为它满足显然，当N，（）逼近一个连续函数。进一步，由矩阵特征值理论有 如果 1，那么就存在一条长为p的闭合回路使得从编号为i1的节点出发经过p1个节点可以返回i1节点。于是，N和Mp的乘积就表示了网络中存在的长为p的闭合回路的总数。当p=3时，由于一个三角形中有6条闭合回路，因此NM36就是图中三角形的数目。而在树状网络中，从一点出发只有经过偶

48、数步才能返回同一节点，故树状网络谱密度的奇数阶矩为0。,84,2.6.3 度秩函数,将图G中的节点按度降序排列成N1段，其中第s段的节点度均为Ns。令ki表示节点vi的度，显然1kiN1，同时称D=k1，k2，kN为图G的度序列。不失一般性，设总有k1k2kN。令ls表示第s段的节点数目，即网络中连接度为Ns的节点数目。令节点vi处于第si段，ri表示节点vi的排序号。定义度序列D中节点的度ki与节点排序号ri之间的关系为图G的度秩函数，记为kf(r)。若节点数为N的图G的节点度分布为P（k），且P（k）可积，则图G的度秩函数为kf（r）NT，其中T满足 无标度网络度分布P（k）Ck-（0），

49、则度秩函数kf（r）（C1r）-。式中，C1（1）（NC），（N1）-+1，1（1）。,85,2.6.4 富人俱乐部系数,网络包含少量的大度节点，这些大度节点称为“富节点”，它们之间以很高的连接概率互联，构成“富人俱乐部”。富人俱乐部系数（r）表示最富有r个节点的总链路数Er与这r个节点之间总的可能存在的共享链路数的最大值r（r1）2的比值，即当（r）0，不存在富人俱乐部；当（r）1，网络所有节点与其他节点都直接相连，形成一个完全连通图。富人俱乐部现象和匹配性是有区别的，二者没有必然联系，从不同观点描述了网络的整体结构。,86,返回 目录,2.7 复杂网络分析软件,研究软件有：Pajek、UC

50、INET、NetworkX、NetMiner3、Igraph、Guess、NetVis等。简单介绍Pajek。通过Pajek可以完成以下工作：在一个网络中搜索类（组成、重要节点的邻居、核等）；析取属于同一类的节点，并分别地显示出来，或者反映节点的连接关系（更具体的局域视角）；在类内收缩节点，并显示类之间的关系。该软件除了能研究普通网络（有向网络、无向网络、混合网络）外，还支持多关系网络、二分网络及动态网络的研究。该软件主要有六种数据结构：网络（networks）、分类（partitions）、排序（permutations）、类（cluster）、层次（hierarchy）、向量（vector