复杂网络基础理论-第二章

复杂网络基础理论第二章网络拓扑结构与静态特征第二章网络拓扑结构与静态特征2.1引言2.2网络的基本静态几何特征2.3无向网络的静态特征2.4有向网络的静态特征2.5加权网络的静态特征2.6网络的其他静态特征2.7复杂网络分析软件22.1引言与图论的研究有所不同，复杂网络的研究更侧重于从各种实际网络的现象之上抽象出一般的网络几何量，并用这些一般性质指导更多实际网络的研究，进而通过讨论实际网络上的具体现象发展网络模型的一般方法，最后讨论网络本身的形成机制。统计物理学在模型研究、演化机制与结构稳定性方面的丰富的研究经验是统计物理学在复杂网络研究领域得到广泛应用的原因；而图论与社会网络分析提供的网络静态几何量及其分析方法是复杂网络研究的基础。32.1引言静态特征指给定网络的微观量的统计分布或宏观统计平均值。在本章中我们将对网络的各种静态特征做一小结。由于有向网络与加权网络有其特有的特征量，我们将分开讨论无向、有向与加权网络。4返回目录2.2网络的基本静态几何特征2.2.1平均距离2.2.2集聚系数2.2.3度分布2.2.4实际网络的统计特征52.2.1平均距离1.网络的直径与平均距离网络中的两节点vi和vj之间经历边数最少的一条简单路径（经历的边各不相同），称为测地线。测地线的边数dij称为两节点vi和vj之间的距离（或叫测地线距离）。1／dij称为节点vi和vj之间的效率，记为εij。通常效率用来度量节点间的信息传递速度。当vi和vj之间没有路径连通时，dij＝∞，而εij＝0，所以效率更适合度量非全通网络。网络的直径D定义为所有距离dij中的最大值62.2.1平均距离平均距离（特征路径长度）L定义为所有节点对之间距离的平均值，它描述了网络中节点间的平均分离程度，即网络有多小，计算公式为对于无向简单图来说，dij＝dji且dii＝0，则上式可简化为很多实际网络虽然节点数巨大，但平均距离却小得惊人，这就是所谓的小世界效应。72.2.1平均距离2.距离与邻接矩阵的关系定义对于无权简单图来说，当l＝1时，。容易证明无权简单图邻接矩阵A的l次幂Al的元素表示节点vi和vj之间通过l条边连接的路径数。当l＝2时，容易推出式中，U表示单位指示函数，即当x＞0，U（x）＝1；否则U（x）＝0。当i＝j时，δij＝1；否则δij＝0。82.2.1平均距离容易用数学归纳法证明据此，若D为网络直径，则两节点vi和vj之间的距离dij可以表示为92.2.2集聚系数首先来看节点的集聚系数定义。假设节点vi与ki个节点直接连接，那么对于无向网络来说，这ki个节点间可能存在的最大边数为ki（ki－1）／2，而实际存在的边数为Mi，由此我们定义Ci＝2Mi／［ki（ki－1）］为节点vi的集聚系数。对于有向网络来说，这ki个节点间可能存在的最大弧数为ki（ki－1），此时vi的集聚系数Ci＝Mi／［ki（ki－1）］。将该集聚系数对整个网络作平均，可得网络的平均集聚系数为102.2.2集聚系数显然，0≤C≤1。当C＝0，所有节点都是孤立节点，没有边连接。当C＝1时，网络为所有节点两两之间都有边连接的完全图。对于完全随机网络来说，当节点数很大时，C→O（1／N）。而许多大规模的实际网络的集聚系数通常远小于1而大于O（1／N)。对于社会网络来说，通常随着N→∞，集聚系数C→O（1），即趋向一个非零常数。节点vi的集聚系数也可定义为Ci＝NiΔ／NiΛ。式中NiΔ代表与节点vi相连的“三角形”数目，数值上就等于Mi；NiΛ代表与节点vi相连的“三元组”数目，即节点vi与其它两个节点都有连接，即“至少与其他两个分别认识”，数值上就等于ki（ki－1）／2。112.2.2集聚系数如何根据无向无权简单图的邻接矩阵A来求节点vi的集聚系数Ci？显然，邻接矩阵二次幂A2的对角元素表示的是与节点vi相连的边数，也就是节点vi的度ki。而邻接矩阵三次幂A3的对角元素＝∑（aij·ajl·ali）（j≠l）表示的是从节点vi出发经过三条边回到节点vi的路径数，也就是与节点vi相连的三角形数的两倍（正向走和反向走）。因此，由集聚系数的定义可知122.2.2集聚系数【例2.1】计算下面简单网络的直径、平均距离和各节点的集聚系数。解：首先计算出所有节点对的距离：d12＝1；d13＝1；d14＝2；d15＝1；d16＝2；d23＝1；d24＝1；d25＝2；d26＝2；d34＝2；d35＝2；d36＝1；d45＝3；d46＝1；d56＝3。由此可得直径和平均距离为132.2.2集聚系数下面以节点v1的集聚系数计算为例：采用第一种定义可知，节点v1与3个节点直接连接，而这3个节点之间可能存在的最大边数为3（3－1）／2，而实际存在的边数为1，由此可得C1＝2／［3（3－1）］＝1／3。若采用第二种定义可知：与相连的三角形数为N1Δ＝１，而与v1相连的三元组数为N1Λ＝3，故C1＝1／3。也可以利用式计算，因为邻接矩阵A的前三次幂为142.2.2集聚系数故＝2，＝3，从而同理可得其他各节点的集聚系数为C2＝1／3；C3＝1／3；C4＝0；C5＝0；C6＝0由此很容易算出该网络的集聚系数152.2.3度分布1.节点的度在网络中，节点vi的邻边数ki称为该节点vi的度。对网络中所有节点的度求平均，可得到网络的平均度＜k＞无向无权图邻接矩阵A的二次幂A2的对角元素就是节点vi的邻边数，即。实际上，无向无权图邻接矩阵A的第i行或第i列元素之和也是度。从而无向无权网络的平均度就是A2对角线元素之和除以节点数，即＜k＞＝tr（A2）／N。式中，tr（A2）表示矩阵A2的迹，即对角线元素之和。162.2.3度分布2.度分布大多数实际网络中的节点的度是满足一定的概率分布的。定义P（k）为网络中度为k的节点在整个网络中所占的比率。规则网络：由于每个节点具有相同的度，所以其度分布集中在一个单一尖峰上，是一种Delta分布。完全随机网络：度分布具有Poisson分布的形式，每一条边的出现概率是相等的，大多数节点的度是基本相同的，并接近于网络平均度＜k＞，远离峰值＜k＞，度分布则按指数形式急剧下降。把这类网络称为均匀网络。无标度网络：具有幂指数形式的度分布：P（k）∝k−γ。所谓无标度是指一个概率分布函数F（x）对于172.2.3度分布任意给定常数a存在常数b使得F（x）满足F（ax）＝bF（x）。幂律分布是唯一满足无标度条件的概率分布函数。许多实际大规模无标度网络，其幂指数通常为2≤γ≤3，绝大多数节点的度相对很低，也存在少量度值相对很高的节点（称为hub），把这类网络称为非均匀网络。指数度分布网络：P（k）∝e−k/к，式中к＞0为一常数。182.2.3度分布3.累积度分布可以用累积度分布函数来描述度的分布情况，它与度分布的关系为它表示度不小于k的节点的概率分布。若度分布为幂律分布，即P（k）∝k−γ，则相应的累积度分布函数符合幂指数为γ－1的幂律分布若度分布为指数分布，即P（k）∝e−k/к，则相应的累积度分布函数符合同指数的指数分布192.2.4实际网络的统计特征20返回目录2.3无向网络的静态特征2.3.1联合度分布和度－度相关性2.3.2集聚系数分布和聚－度相关性2.3.3介数和核度2.3.4中心性2.3.5网络密度2.3.6连通集团（子图）及其规模分布212.3.1联合度分布和度－度相关性1.联合度分布度分布满足平均度与度分布具有关系式联合度分布定义为从无向网络中随机选择一条边，该边的两个节点的度值分别为k1和k2的概率，即式中，M（k1，k2）为度值为k1的节点和度值为k2的节点相连的总边数，M为网络总边数。从联合度分布可以得出度分布式中，＝1（k＝k2）；＝0（k≠k2）。222.3.1联合度分布和度－度相关性联合节点度分布所包含的拓扑信息最多，节点度分布次之，平均节点度最少。2.基于最近邻平均度值的度－度相关性度－度相关性描述了网络中度大的节点和度小的节点之间的关系。若度大的节点倾向于和度大的节点连接，则网络是度－度正相关的；反之，若度大的节点倾向于和度小的节点连接，则网络是度－度负相关的。节点vi的最近邻平均度值定义为式中，ki表示节点vi的度值，aij为邻接矩阵元素。232.3.1联合度分布和度－度相关性所有度值为k的节点的最近邻平均度值的平均值knn（k）定义为式中，N为节点总数，P（k）为度分布函数。如果knn（k）是随着k上升的增函数，则说明度值大的节点倾向于和度值大的节点连接，网络具有正相关特性，称之为同配网络；反之网络具有负相关特性，称之为异配网络。3.基于Pearson相关系数的度－度相关性Newman利用边两端节点的度的Pearson相关系数r来描述网络的度－度相关性，具体定义为242.3.1联合度分布和度－度相关性式中，ki，kj分别表示边eij的两个节点vi，vj的度，M表示网络的总边数。容易证明度－度相关系数r的范围为：0≤|r|≤1。当r0时，网络是负相关的；当r0时，网络是正相关的；当r＝0时，网络是不相关的。252.3.2集聚系数分布和聚－度相关性1.集聚系数分布集聚系数分布函数P（C）表示从网络中任选一节点，其集聚系数值为C的概率式中，δ（x）为单位冲激函数。2.聚－度相关性局部集聚系数C（k）定义为度为k的节点的邻居之间存在的平均边数＜Mnn（k）＞与这些邻居之间存在的最大可能的边数的比值，即262.3.2集聚系数分布和聚－度相关性全局集聚系数C则定义为式中，＜k2＞为度的二阶矩。显然，局部集聚系数C（k）与k的关系刻画了网络的聚－度相关性。许多真实网络如好莱坞电影演员合作网络、语义网络中节点的聚－度相关性存在近似的倒数关系C（k）∝k−1。把这种倒数关系的聚－度相关性称为层次性，把具有层次性的网络称为层次网络。272.3.3介数和核度1.介数要衡量一个节点的重要性，其度值当然可以作为一个衡量指标，但又不尽然，例如在社会网络中，有的节点的度虽然很小，但它可能是两个社团的中间联络人，如果去掉该节点，那么就会导致两个社团的联系中断，因此该节点在网络中起到极其重要的作用。对于这样的节点，需要定义另一种衡量指标，这就引出网络的另一种重要的全局几何量——介数。介数分为节点介数和边介数两种，反映了节点或边在整个网络中的作用和影响力。282.3.3介数和核度节点的介数Bi定义为式中，Njl表示节点vj和vl之间的最短路径条数，Njl（i）表示节点vj和vl之间的最短路径经过节点vi的条数。边的介数Bij定义为式中，Nlm表示节点vl和vm之间的最短路径条数，Nlm（eij）表示节点vl和vm之间的最短路径经过边eij的条数。292.3.3介数和核度2.介数分布和介－度相关性节点的介数与度之间有很强的相关性，而且不同类型的网络，其介数分布也大不一样。介－度相关性可以用B（k）～k表示，它定义为所有度为k的节点的介数平均值随着k的变化关系。节点介数分布Pv（B）定义为网络中节点介数为B的节点数占网络节点总数的比例。边介数分布Pe（B）定义为网络中边介数为B的边数占网络总边数的比例。研究表明，节点的最大介数与网络的同步能力密切相关：节点的最大介数越大，网络的同步能力越弱。302.3.3介数和核度3.核度一个图的k－核是指反复去掉度值小于k的节点及其连线后，所剩余的子图，该子图的节点数就是该核的大小。若一个节点属于k－核，而不属于（k＋1）－核，则此节点的核度为k。节点核度的最大值叫做网络的核度。节点的核度可以说明节点在核中的深度，核度的最大值自然就对应着网络结构中最中心的位置。k－核解析可用来描述度分布所不能描述的网络特征，揭示源于系统特殊结构的结构和层次性质。312.3.3介数和核度【例2.2】计算下面网络的一些特性：（1）度分布及平均度；（2）联合度分布[并验证的正确性]；（3）各节点的最近邻平均度值knn,i；（4）该网络是否是同配网络；（5）该网络是否是正相关网络；（6）分别求各节点和各连接边的介数；（7）求该网络的2－核