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

《复杂网络基础理论-第二章ppt课件.ppt》由会员分享，可在线阅读，更多相关《复杂网络基础理论-第二章ppt课件.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能复杂网络基础理论复杂网络基础理论第二章第二章 网络拓扑结构与静态特征网络拓扑结构与静态特征为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第二章 网络拓扑结构与静态特征l2.1 引言l2.2 网络的基本静态几何特征l2.3 无向网络的静态特征l2.4 有向网络的静态特征l2.5 加权网络的静态特征l2.6 网络的其他静态特征l2.7 复杂网络分析软件2 2为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教

2、育大会精神,充分发挥中小学图书室育人功能2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重于从各种实际网络的现象之上抽象出一般的网络几何量，并用这些一般性质指导更多实际网络的研究，进而通过讨论实际网络上的具体现象发展网络模型的一般方法，最后讨论网络本身的形成机制。统计物理学在模型研究、演化机制与结构稳定性方面的丰富的研究经验是统计物理学在复杂网络研究领域得到广泛应用的原因；而图论与社会网络分析提供的网络静态几何量及其分析方法是复杂网络研究的基础。3 3为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1 引言 静态特征指给定

3、网络的微观量的统计分布或宏观统计平均值。在本章中我们将对网络的各种静态特征做一小结。由于有向网络与加权网络有其特有的特征量，我们将分开讨论无向、有向与加权网络。返回 目录4 4为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2 网络的基本静态几何特征2.2.1 平均距离2.2.2 集聚系数2.2.3 度分布2.2.4 实际网络的统计特征5 5为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.1 平均距离1.网络的直径与平均距离 网络中的两节点vi和vj之间经历边

4、数最少的一条简单路径（经历的边各不相同），称为测地线。测地线的边数dij称为两节点vi和vj之间的距离（或叫测地线距离）。1dij称为节点vi和vj之间的效率，记为ij。通常效率用来度量节点间的信息传递速度。当vi和vj之间没有路径连通时，dij，而ij0，所以效率更适合度量非全通网络。网络的直径D定义为所有距离dij中的最大值6 6为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.1 平均距离 平均距离（特征路径长度）L定义为所有节点对之间距离的平均值，它描述了网络中节点间的平均分离程度，即网络有多小，计算公式为 对于无向简

5、单图来说，dijdji且dii0，则上式可简化为 很多实际网络虽然节点数巨大，但平均距离却小得惊人，这就是所谓的小世界效应。7 7为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.1 平均距离2.距离与邻接矩阵的关系 定义对于无权简单图来说，当l1时，。容易证明无权简单图邻接矩阵A的l次幂Al的元素 表示节点vi和vj之间通过l条边连接的路径数。当l2时，容易推出式中，U表示单位指示函数，即当x0，U（x）1；否则U（x）0。当ij时，ij1；否则ij0。8 8为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全

6、国教育大会精神,充分发挥中小学图书室育人功能2.2.1 平均距离 容易用数学归纳法证明据此，若D为网络直径，则两节点vi和vj之间的距离dij可以表示为9 9为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.2 集聚系数 首先来看节点的集聚系数定义。假设节点vi与ki个节点直接连接，那么对于无向网络来说，这ki个节点间可能存在的最大边数为ki（ki1）2，而实际存在的边数为Mi，由此我们定义Ci2Miki（ki1）为节点vi的集聚系数。对于有向网络来说，这ki个节点间可能存在的最大弧数为ki（ki1），此时vi的集聚系数CiM

7、iki（ki1）。将该集聚系数对整个网络作平均，可得网络的平均集聚系数为1010为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.2 集聚系数 显然，0C1。当C0，所有节点都是孤立节点，没有边连接。当C1时，网络为所有节点两两之间都有边连接的完全图。对于完全随机网络来说，当节点数很大时，CO（1N）。而许多大规模的实际网络的集聚系数通常远小于1而大于O（1N)。对于社会网络来说，通常随着N，集聚系数CO（1），即趋向一个非零常数。节点vi的集聚系数也可定义为CiNiNi。式中Ni代表与节点vi相连的“三角形”数目，数值上就等

8、于Mi；Ni代表与节点vi相连的“三元组”数目，即节点vi与其它两个节点都有连接，即“至少与其他两个分别认识”，数值上就等于ki（ki1）2。1111为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.2 集聚系数 如何根据无向无权简单图的邻接矩阵A来求节点vi的集聚系数Ci？显然，邻接矩阵二次幂A2的对角元素 表示的是与节点vi相连的边数，也就是节点vi的度ki。而邻接矩阵三次幂A3的对角元素 （aijajlali）（jl）表示的是从节点vi出发经过三条边回到节点vi的路径数，也就是与节点vi相连的三角形数的两倍（正向走和反向

9、走）。因此，由集聚系数的定义可知1212为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.2 集聚系数【例例2.1】计算下面简单网络的直径、平均距离和各节点的集聚系数。解：首先计算出所有节点对的距离：d121；d131；d142；d151；d162；d231；d241；d252；d262；d342；d352；d361；d453；d461；d563。由此可得直径和平均距离为1313为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.2 集聚系数 下面以节点v1的集

10、聚系数计算为例：采用第一种定义可知，节点v1与3个节点直接连接，而这3个节点之间可能存在的最大边数为3（31）2，而实际存在的边数为1，由此可得C123（31）13。若采用第二种定义可知：与相连的三角形数为N1，而与v1相连的三元组数为N13，故C113。也可以利用式 计算，因为邻接矩阵A的前三次幂为1414为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.2 集聚系数故 2，3，从而同理可得其他各节点的集聚系数为C213；C313；C40；C50；C60由此很容易算出该网络的集聚系数1515为深入学习习近平新时代中国特色社会

11、主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.3 度分布1.节点的度 在网络中，节点vi的邻边数ki称为该节点vi的度。对网络中所有节点的度求平均，可得到网络的平均度k 无向无权图邻接矩阵A的二次幂A2的对角元素 就是节点vi的邻边数，即 。实际上，无向无权图邻接矩阵A的第i行或第i列元素之和也是度。从而无向无权网络的平均度就是A2对角线元素之和除以节点数，即ktr（A2）N。式中，tr（A2）表示矩阵A2的迹，即对角线元素之和。1616为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.3

12、 度分布2.度分布 大多数实际网络中的节点的度是满足一定的概率分布的。定义P（k）为网络中度为k的节点在整个网络中所占的比率。规则网络：由于每个节点具有相同的度，所以其度分布集中在一个单一尖峰上，是一种Delta分布。完全随机网络：度分布具有Poisson分布的形式，每一条边的出现概率是相等的，大多数节点的度是基本相同的，并接近于网络平均度k，远离峰值k，度分布则按指数形式急剧下降。把这类网络称为均匀网络。无标度网络：具有幂指数形式的度分布：P（k）k。所谓无标度是指一个概率分布函数F（x）对于1717为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中

13、小学图书室育人功能2.2.3 度分布任意给定常数a存在常数b使得F（x）满足F（ax）bF（x）。幂律分布是唯一满足无标度条件的概率分布函数。许多实际大规模无标度网络，其幂指数通常为23，绝大多数节点的度相对很低，也存在少量度值相对很高的节点（称为hub），把这类网络称为非均匀网络。指数度分布网络：P（k）ek/，式中0为一常数。1818为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.3 度分布3.累积度分布 可以用累积度分布函数来描述度的分布情况，它与度分布的关系为它表示度不小于k的节点的概率分布。若度分布为幂律分布，即P

14、（k）k，则相应的累积度分布函数符合幂指数为1的幂律分布 若度分布为指数分布，即P（k）ek/，则相应的累积度分布函数符合同指数的指数分布1919为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.4 实际网络的统计特征返回 目录2020为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3 无向网络的静态特征2.3.1 联合度分布和度度相关性2.3.2 集聚系数分布和聚度相关性2.3.3 介数和核度2.3.4 中心性2.3.5 网络密度2.3.6 连通集团（子图）及

15、其规模分布2121为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.1 联合度分布和度度相关性1.联合度分布 度分布满足 平均度与度分布具有关系式 联合度分布定义为从无向网络中随机选择一条边，该边的两个节点的度值分别为k1和k2的概率，即式中，M（k1，k2）为度值为k1的节点和度值为k2的节点相连的总边数，M为网络总边数。从联合度分布可以得出度分布式中，1（kk2）；0（kk2）。2222为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.1 联合度分布和度度

16、相关性 联合节点度分布所包含的拓扑信息最多，节点度分布次之，平均节点度最少。2.基于最近邻平均度值的度度相关性 度度相关性描述了网络中度大的节点和度小的节点之间的关系。若度大的节点倾向于和度大的节点连接，则网络是度度正相关的；反之，若度大的节点倾向于和度小的节点连接，则网络是度度负相关的。节点vi的最近邻平均度值定义为式中，ki表示节点vi的度值，aij为邻接矩阵元素。2323为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.1 联合度分布和度度相关性 所有度值为k的节点的最近邻平均度值的平均值knn（k）定义为式中，N为节点

17、总数，P（k）为度分布函数。如果knn（k）是随着k上升的增函数，则说明度值大的节点倾向于和度值大的节点连接，网络具有正相关特性，称之为同配网络；反之网络具有负相关特性，称之为异配网络。3.基于Pearson相关系数的度度相关性 Newman利用边两端节点的度的Pearson相关系数r来描述网络的度度相关性，具体定义为2424为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.1 联合度分布和度度相关性式中，ki，kj分别表示边eij的两个节点vi，vj的度，M表示网络的总边数。容易证明度度相关系数r的范围为：0|r|1。当r0

18、时，网络是正相关的；当r0时，网络是不相关的。2525为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.2 集聚系数分布和聚度相关性1.集聚系数分布 集聚系数分布函数P（C）表示从网络中任选一节点，其集聚系数值为C的概率式中，（x）为单位冲激函数。2.聚度相关性 局部集聚系数C（k）定义为度为k的节点的邻居之间存在的平均边数Mnn（k）与这些邻居之间存在的最大可能的边数的比值，即2626为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.2 集聚系数分布和聚度相

19、关性 全局集聚系数C则定义为式中，k2为度的二阶矩。显然，局部集聚系数C（k）与k的关系刻画了网络的聚度相关性。许多真实网络如好莱坞电影演员合作网络、语义网络中节点的聚度相关性存在近似的倒数关系C（k）k1。把这种倒数关系的聚度相关性称为层次性，把具有层次性的网络称为层次网络。2727为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.3 介数和核度1.介数 要衡量一个节点的重要性，其度值当然可以作为一个衡量指标，但又不尽然，例如在社会网络中，有的节点的度虽然很小，但它可能是两个社团的中间联络人，如果去掉该节点，那么就会导致两个

20、社团的联系中断，因此该节点在网络中起到极其重要的作用。对于这样的节点，需要定义另一种衡量指标，这就引出网络的另一种重要的全局几何量介数。介数分为节点介数和边介数两种，反映了节点或边在整个网络中的作用和影响力。2828为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.3 介数和核度 节点的介数Bi定义为式中，Njl表示节点vj和vl之间的最短路径条数，Njl（i）表示节点vj和vl之间的最短路径经过节点vi的条数。边的介数Bij定义为式中，Nlm表示节点vl和vm之间的最短路径条数，Nlm（eij）表示节点vl和vm之间的最短路

21、径经过边eij的条数。2929为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.3 介数和核度2.介数分布和介度相关性 节点的介数与度之间有很强的相关性，而且不同类型的网络，其介数分布也大不一样。介度相关性可以用B（k）k表示，它定义为所有度为k的节点的介数平均值随着k的变化关系。节点介数分布Pv（B）定义为网络中节点介数为B的节点数占网络节点总数的比例。边介数分布Pe（B）定义为网络中边介数为B的边数占网络总边数的比例。研究表明，节点的最大介数与网络的同步能力密切相关：节点的最大介数越大，网络的同步能力越弱。3030为深入学

22、习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.3 介数和核度3.核度 一个图的k核是指反复去掉度值小于k的节点及其连线后，所剩余的子图，该子图的节点数就是该核的大小。若一个节点属于k核，而不属于（k1）核，则此节点的核度为k。节点核度的最大值叫做网络的核度。节点的核度可以说明节点在核中的深度，核度的最大值自然就对应着网络结构中最中心的位置。k核解析可用来描述度分布所不能描述的网络特征，揭示源于系统特殊结构的结构和层次性质。3131为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室

23、育人功能2.3.3 介数和核度【例例2.2】计算下面网络的一些特性：（1）度分布及平均度；（2）联合度分布并验证 的正确性；（3）各节点的最近邻平均度值knn,i；（4）该网络是否是同配网络；（5）该网络是否是正相关网络；（6）分别求各节点和各连接边的介数；（7）求该网络的2核，3核及各自核度大小，并计算该网络的核度。3232为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.3 介数和核度解：（1）该网络的度分布如下表所示。因此或（2）根据 容易得到联合度分布如下表所示。由此可以验证 的正确性，例如当k1时，该式左边P（1）=

24、16，而右边为3333为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.3 介数和核度（3）利用 得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；v2

25、e5v4；v2e2v1e1v5；v2e4v3e7v6；v2e5v4e6v6；v3e4v2e5v4；v3e7v6e6v4；v3e3v1e1v5；v3e7v6；v4e5v2e2v1e1v5；v4e6v6；v5e1v1e3v3e7v6。3434为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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

26、、2、1、2，所以网络的核度为3。3535为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.4 中心性1.度中心性 度中心性分为节点度中心性和网络度中心性。前者指的是节点在其与之直接相连的邻居节点当中的中心程度，而后者则侧重节点在整个网络的中心程度，表征的是整个网络的集中或集权程度，即整个网络围绕一个节点或一组节点来组织运行的程度。节点vi的度中心性CD（vi）定义为 在所有含N节点的网络中，假设网络Goptimal使得下式达到最大值式中，ui为网络Goptimal的各个节点，u max表示网络Goptimal中拥有最大度中心

27、性的节点。3636为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.4 中心性 对于含N节点的某网络G，令vmax表示其拥有最大度中心性的节点，则网络G的度中心性CD定义为 当图Goptimal为星型网络时，H值达到最大，即 因此，网络G的度中心性CD可简化为3737为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.4 中心性2.介数中心性 介数中心性分为节点介数中心性和网络介数中心性。节点vi的介数中心性CB（vi）定义为 与度中心性类似，可得HN1（也是星

28、型网络，中心节点的介数中心性为1，其它节点的介数中心性为0）。因此，网络G的介数中心性CB可简化为3838为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.4 中心性3.接近度中心性 对于连通图来说，节点vi的接近度中心性CC（vi）定义为 与度中心性类似，可得H（N1）（N2）（2N3）（也是星型网络）。因此，连通网络G的接近度中心性CC可简化为 对于非连通图来说，上述定义需要做一定的修正，一个比较好的做法是分别计算各个连通分支的中心性，然后根据各连通分支的阶数进行加权。3939为深入学习习近平新时代中国特色社会主义思想和党

29、的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.4 中心性4.特征向量中心性Axx 通常，上式的各个特征向量对应不同的特征值。在这里，一个额外的要求是特征向量的每个分量必须是正数。根据PerronFrobenius定理，只有最大的特征值对应的特征向量才是中心性测度所需要的。求这个特征向量可采用幂迭代算法。在最后得到的特征向量中，第i个分量xi就是节点vi的特征向量中心性CE（vi）。4040为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.5 网络密度 网络密度指的是一个网络中各节点之间联络的紧密程度。

30、网络G的网络密度d（G）定义为式中，M为网络中实际拥有的连接数，N为网络节点数。网络密度的取值范围为0，1，当网络内部完全连通时，网络密度为1，而实际网络的密度通常远小于1，实际网络中能够发现的最大密度值是0.5。不同规模网络的密度无法进行比较。为了解决这一问题，John Scott提出了“绝对密度”公式式中，D表示网络直径，R表示半径，S表示根据直径算出的圆周长。4141为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.6 连通集团（子图）及其规模分布1.连通、连通集团（子图）和连通分支（最大连通子图）连通集团（子图）就是指

31、网络G中的一个子图，在这个子图内，任意两个节点之间都至少存在一条简单路径。对于非连通图G来说，肯定可以将其分解为两个或两个以上的连通分支。所谓连通分支就是最大连通子图，即该连通子图加入任何其它节点都将影响该子图的连通性。图G中的每个节点只能属于一个连通分支，边也一样。显然，连通图的连通分支数为1，而非连通图的连通分支数大于1。把网络的各连通分支中阶数最大的一个称为最大连通分支。4242为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.6 连通集团（子图）及其规模分布2.连通度 连通图G的连通程度通常叫做连通度。连通度有两种，一

32、种是点连通度，一种是边连通度。通常一个图的连通度越好，它所代表的网络越稳定。点连通度定义为式中，V是图G的节点集合，S为V的真子集，（GS）表示从图G中删除点集S后得到的子图GS的连通分支数。这里GS是指删除S中每一个节点以及图G中与之关联的所有边。由此可见，点连通度就是使G不连通或成为平凡图所必须删除的最少节点个数。对于不连通图或平凡图，定义（G）0；若G为N阶完全图，（G）N1。4343为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.6 连通集团（子图）及其规模分布 边连通度定义为式中，E是图G的边集合，T为E的真子集，

33、（GT）表示从图G中删除边集T后得到的子图GT的连通分支数。这里GT是指删除T中每一条边，而G中所有节点全部保留下来。由此可见，边连通度就是使G不连通所必须删除的最少边数。对于不连通图或平凡图，定义（G）0；若G为N阶完全图，（G）N1。可以证明，同一个图的点连通度和边连通度满足（G）（G）。4444为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.6 连通集团（子图）及其规模分布3.连通集团的规模分布 连通集团的规模分布反映了网络G中的各种规模的连通分支的数目分布情况。实证研究表明，对于大量的无标度网络，连通集团的规模也存在

34、幂律分布。例如，科学家合作网的连通子图规模分布。返回 目录4545为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4 有向网络的静态特征2.4.1 入度和出度及其分布2.4.2 度度相关性2.4.3 平均距离和效率2.4.4 入集团和出集团的集聚程度2.4.5 介数和双向比2.4.6 中心性4646为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.1 入度和出度及其分布1.入度与出度 由于与有向网络某个节点相关联的弧有指向节点的，也有背向节点向外的，因此除了可以

35、统计与某个节点相关联的弧数，也就是度之外，有必要分开统计两个方向的弧数，分别称为节点的入度和出度。节点vi的入度、出度和有向图的邻接矩阵以及度的关系为4747为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.1 入度和出度及其分布 同平均度一样，也可以求平均入度kin和平均出度kout为2.入度分布和出度分布 入度分布和出度分布分别记为Pin（k）和Pout（k），分别表示网络中任意取出一个节点，其入度值和出度值刚好为k的概率。入（出）度分布与平均入（出）度之间具有如下关系式4848为深入学习习近平新时代中国特色社会主义思想和

36、党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.1 入度和出度及其分布3.累积入度分布和累积出度分布 累积入（出）度分布与入（出）度分布的关系为 容易证明入（出）度幂律分布对应的累积分布也是幂律分布，入（出）度指数分布对应的累积分布也是同指数的指数分布。4.联合度分布 联合度分布有两种定义方式，第一种定义方式是基于弧的方式，第二种定义方式是基于节点的方式。4949为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.1 入度和出度及其分布 基于弧的方式：从网络中随机选择一条弧，该弧由入度和出度分别为（ji

37、n，jout）的节点连向入度和出度分别为（kin，kout）的节点的概率，即式中，M（jin，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）的概率5050为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人

38、功能2.4.1 入度和出度及其分布 若对上式按照（jin，jout）求和，就得到随机选取一条弧，该弧终点的度为（kin，kout）的概率 基于节点的方式：从网络中随机选择一个节点，其入度值和出度值分别为kin和kout的概率，即式中，N（kin，kout）为入度值和出度值分别为kin和kout的节点数，N为网络总节点数。Pv（kin，kout）和Pf（kin，kout）、Pt（kin，kout）具有如下关系式5151为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.2 度度相关性 度度相关性也有两种定义方式，即基于节点的方式和

39、基于弧的方式。1.基于节点的入度出度相关性 可以定义节点的入度为kin的情况下其出度为kout的条件概率为 然后，可以定义基于节点的入度出度相关性为 更简便的定义为 如果kvv（kin）kin曲线的斜率小于0，则kin和kout负相关；斜率大于0，则kin和kout正相关；等于0，则kin和kout不相关。5252为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.2 度度相关性2.基于弧的度度相关性 任意选取一条弧，在弧的两端存在两个度值，起点的入度和出度，终点的入度和出度，所以存在四种相关性，分别是起点入度终点入度，起点出度

40、终点入度，终点入度起点出度以及终点出度起点出度,分别记做kin-in（kin）kin，kout-in（kin）kin，kin-out（kout）kout，kout-out（kout）kout。这四种相关性可分别定义如下5353为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.3 平均距离和效率 由于有向网络里的弧是带有方向的，所以从节点vi到vj之间的距离dij和从节点vj到vi之间的距离dji是不同的。距离dij定义为从节点vi出发沿着同一方向到达节点vj所要经历的弧的最少数目，而它的倒数1dij称为从节点vi到节点vj的效

41、率，记为ij。有向连通简单网络的平均距离L定义为所有节点对之间距离的平均值，定义为 因为效率可以用来描述非连通网络，所以可以定义有向网络的效率LC为5454为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.4 入集团和出集团的集聚程度 对于某个节点vi来说，所有以该节点为终点的弧的起始节点及它们之间的连弧构成一个小集团，称之为入集团；而所有以该节点为起点的弧的终止节点及它们之间的连弧构成一个小集团，称之为出集团。由于节点vi的入度为kiin，则连向该节点的kiin个起始节点间可能存在的最大弧数为kiin（kiin1），而实际存

42、在的弧数为Miin，由此定义为节点vi的入集聚系数，然后将该集聚系数对整个网络作平均，即可得网络的入集团的集聚系数。5555为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.4 入集团和出集团的集聚程度 同理，定义为节点vi的出集聚系数，然后将该集聚系数对整个网络作平均，即可得网络的出集团的集聚系数。5656为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.4 入集团和出集团的集聚程度【例例2.3】针对下图所示网络分别计算：（1）写出该网络的邻接矩阵、入度分布

43、及出度分布；（2）分别求出该网络的Pf（kin，kout）、Pt（kin，kout）和Pv（kin，kout）；（3）整个网络的入集团和出集团的集聚系数。5757为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.4 入集团和出集团的集聚程度解：（1）该网络的邻接矩阵为 入度分布如下表所示 出度分布如下表所示（2）联合概率分布Pe（jin，jout；kin，kout）如下表所示5858为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.4 入集团和出集团的集聚程度

44、 由上表可得Pf（jin，jout），如下表所示 Pt（kin，kout）如下表所示 Pv（kin，kout）如下表所示5959为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.4 入集团和出集团的集聚程度（3）以节点v5为例，其对应的入集团如下图所示，由此可计算出节点v5的入集团集聚系数同理可计算出每个节点的入集团的集聚系数为：0、0、0、12、16、0。而每个节点的出集团的集聚系数为：12、0、0、0、0、13。因此，可得网络的入集团和出集团集聚系数分别为19和536。6060为深入学习习近平新时代中国特色社会主义思想和党

45、的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.5 介数和双向比1.介数 节点的介数Bi定义为式中，Njl表示从节点vj到vl的最短路径条数，Njl（i）表示从节点vj到vl的最短路径经过节点vi的条数。边的介数Bij定义为式中，Nlm表示从节点vl到vm的最短路径条数，Nlm（eij）表示从节点vl到vm的最短路径经过边eij（方向相同）的条数。6161为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.5 介数和双向比2.双向比 双向比，即两两节点间双向边的总数占网络所有边的比例。假设有向图中含有MB

46、条双向边，则双向比就是：RBMBM。例如下图所示的有向图，其双向比为0.5。6262为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4.6 中心性1.入度中心性和出度中心性 节点vi的入度中心性CD_in（vi）定义为 令vmax表示网络G中拥有最大入度中心性的节点，则网络G的入度中心性定义为 节点vi的出度中心性CD_out（vi）定义为 令vmax表示网络G中拥有最大出度中心性的节点，则网络G的出度中心性定义为6363为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功

47、能2.4.6 中心性2.介数中心性 节点vi的介数中心性CB（vi）定义为 令vmax表示网络G中拥有最高介数中心性的节点，则网络G的介数中心性CB定义为返回 目录6464为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.5 加权网络的静态特征2.5.1 点权、单位权和权重分布差异性2.5.2 权度相关性和权权相关性2.5.3 距离分布和平均距离2.5.4 加权集聚系数2.5.5 介数分布和漏斗效应2.5.6 有向加权网络的最短路径问题6565为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发

48、挥中小学图书室育人功能2.5.1 点权、单位权和权重分布差异性1.点权 节点vi的点权Si定义为式中，Ni表示节点vi的邻点集合，wij表示连接节点vi和节点vj的边的权重。对于无向加权网络，点权Si还可以用邻接矩阵元素表示为式中，aij为邻接矩阵元素（若节点vi与vj无连接则aij0，若有连接则aij1）。对于有向加权网络，可定义入权和出权。6666为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.5.1 点权、单位权和权重分布差异性 入权Siin为以节点vi为终点的所有弧的边权之和，而出权Siout为以节点vi为起点的所有弧的

49、边权之和，即而点权满足2.单位权 单位权表示节点连接的平均权重，它定义为 对于有向加权网络，也可以分别定义单位入权和单位出权如下6767为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.5.1 点权、单位权和权重分布差异性3.权重分布的差异性 节点vi的权重分布差异性Yi表示与节点vi相连的边权分布的离散程度，定义为 对于无向加权网络，可以用邻接矩阵表示为 差异性与度有如下关系：如果与节点vi关联的边的权重值差别不大，则Yi1ki；如果权值相差较大，例如只有一条边的权重起主要作用，则Yi1。对于有向加权网络，也可以分别定义入权差异

50、性和出权差异性，即6868为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.5.2 权度相关性和权权相关性1.基于节点的权度相关性 基于节点的权度相关性指的是对于单个节点来说，其点权和其度之间的相关性。对于无向网络，就是S和k的关系，其定义为式中，N为节点总数，P（k）为度分布函数。当边权与网络拓扑结构无关时，通常呈现Svv（k）wk的分布情况，其中w表示所有边权的平均值；当边权与网络拓扑结构有关时，通常呈现Svv（k）Ak的分布情况（要么指数1，要么常数A）。对于有向网络，除了S和k的关系，还有Sinkin，Sinkout，So