复杂网络基础理论

1、LOGO复杂网络基础理论复杂网络基础理论网络科学理论发展的三个时期网络科学理论发展的三个时期u规则网络理论阶段规则网络理论阶段u随机网络理论阶段随机网络理论阶段u复杂网络理论阶段复杂网络理论阶段u复杂网络的概念复杂网络的概念u复杂网络的特性复杂网络的特性复杂网络的概念和特性复杂网络的概念和特性u1.系统和网络系统和网络u2.复杂性复杂性u3.复杂系统复杂系统u4.复杂网络复杂网络复杂网络的概念复杂网络的概念u复杂性复杂性u小世界特性小世界特性u无标度特性无标度特性u超家族特性超家族特性复杂网络的特性复杂网络的特性IP地址地址网网朋友朋友关关系系网网u概率论基础概率论基础u数理统计基础数理统计基

2、础u统计假设及检验统计假设及检验u一元线性回归分析一元线性回归分析数理统计基础数理统计基础u图的基本概念图的基本概念u图的路和连通性图的路和连通性u图的基本运算图的基本运算u树与生成树树与生成树u图的矩阵表示图的矩阵表示图论的基本概念图论的基本概念研究的主要内容包括：网络的几何性质，网络研究的主要内容包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模的形成机制，网络演化的统计规律，网络上的模型性质，网络的结构稳定性，网络的演化动力学型性质，网络的结构稳定性，网络的演化动力学机制等。机制等。 主要研究工作包括以下几个方面：主要研究工作包括以下几个方面： 1. 1.网络的结构和性

3、质网络的结构和性质 2. 2.网络宏观性质的微观生成机制（网络建模）网络宏观性质的微观生成机制（网络建模） 3. 3.网络上的动力学行为和网络本身的动力学行网络上的动力学行为和网络本身的动力学行为为 4. 4.复杂网络的应用复杂网络的应用 5. 5.复杂网络领域的挑战性问题复杂网络领域的挑战性问题u复杂网络的研究意义复杂网络的研究意义 以复杂网络的形式来研究复杂系统，可以加深人以复杂网络的形式来研究复杂系统，可以加深人们对复杂系统结构上的深入了解。利用复杂网络的们对复杂系统结构上的深入了解。利用复杂网络的研究成果，也可以更加深刻的认识自然界和社会上研究成果，也可以更加深刻的认识自然界和社会上的

4、复杂性，对于我们认识自然界和社会上的各种现的复杂性，对于我们认识自然界和社会上的各种现象和事件有着重要意义。复杂网络的研究为我们提象和事件有着重要意义。复杂网络的研究为我们提供了一种复杂性研究的新视角、新方法，并且提供供了一种复杂性研究的新视角、新方法，并且提供了一种比较的视野，使得我们可以对各种真实网络了一种比较的视野，使得我们可以对各种真实网络进行比较、研究和综合概括。因此，复杂网络研究进行比较、研究和综合概括。因此，复杂网络研究无论在理论上还是实际应用中都有着重要意义。无论在理论上还是实际应用中都有着重要意义。第二章第二章 网络拓扑结构与静态特征网络拓扑结构与静态特征u 静态特征指给定网

5、络的微观量的统计分布或宏观静态特征指给定网络的微观量的统计分布或宏观统计平均值。统计平均值。u在本章中我们将对网络的各种静态特征做一小结在本章中我们将对网络的各种静态特征做一小结。由于有向网络与加权网络有其特有的特征量，我。由于有向网络与加权网络有其特有的特征量，我们将分开讨论无向、有向与加权网络。们将分开讨论无向、有向与加权网络。网络的基本静态几何特征网络的基本静态几何特征u平均距离平均距离u集聚系数集聚系数u度分布度分布u实际网络的统计特征实际网络的统计特征u平均距离平均距离（特征路径长度）（特征路径长度）L定义为所有节点对之间距离的定义为所有节点对之间距离的平均值，它描述了网络中节点间的

6、平均分离程度，即网络有多平均值，它描述了网络中节点间的平均分离程度，即网络有多小，计算公式小，计算公式为为u 对于无向简单图来说，对于无向简单图来说，dijdji且且dii0，则，则上上式可简化为式可简化为u 集聚系数集聚系数 对于无向网络中节点对于无向网络中节点Vi集聚系数定义为集聚系数定义为 C=2Miki（ki1） 对于有向网络来说集聚系数为对于有向网络来说集聚系数为 C=Miki（ki1） 根据邻接矩阵求集聚系数公式为：根据邻接矩阵求集聚系数公式为：度分布度分布u大多数实际网络中的节点的度是满足一定的概率分布的。定大多数实际网络中的节点的度是满足一定的概率分布的。定义义P（k）为网络中

7、度为）为网络中度为k的节点在整个网络中所占的比率的节点在整个网络中所占的比率。 规则规则网络：网络：由于每个节点具有相同的度，所以其度分布集中由于每个节点具有相同的度，所以其度分布集中 在一个单一尖峰上，是一种在一个单一尖峰上，是一种Delta分布分布。 完全随机网络：完全随机网络：度分布具有度分布具有Poisson分布的形式，每一条分布的形式，每一条 边的出现概率是相等的，大多数节点的度是基本相同的边的出现概率是相等的，大多数节点的度是基本相同的。 无标度网络：无标度网络：具有幂指数形式的度分布：具有幂指数形式的度分布：P（k）k 。 指数度分布网络：指数度分布网络： P（k）ek/，式中式

8、中0为一常数为一常数。u累积度分布累积度分布 若度分布为幂律分布，即若度分布为幂律分布，即P（k）k，则相应的累积度，则相应的累积度分布函数符合幂指数为分布函数符合幂指数为1的幂律分布的幂律分布 若度分布为指数分布，即若度分布为指数分布，即P（k）ek/，则则相应的累积相应的累积度分布函数符合同指数的指数分布度分布函数符合同指数的指数分布 实际网络的统计特征实际网络的统计特征无向网络的静态特征无向网络的静态特征u 联合度分布联合度分布 联合度分布定义为从无向网络中随机选择一条边，该边的联合度分布定义为从无向网络中随机选择一条边，该边的两个节点的度值分别为两个节点的度值分别为k1和和k2的概率，

9、即的概率，即u度度相关性度度相关性 度度相关性描述了网络中度大的节点和度小的节点之间度度相关性描述了网络中度大的节点和度小的节点之间的关系。若度大的节点倾向于和度大的节点连接，则网络是度的关系。若度大的节点倾向于和度大的节点连接，则网络是度度正相关的；反之，若度大的节点倾向于和度小的节点连接度正相关的；反之，若度大的节点倾向于和度小的节点连接，则网络是度度负相关的。，则网络是度度负相关的。 集聚系数分布和聚度相关性集聚系数分布和聚度相关性u集聚系数分布集聚系数分布 集聚系数分布函数集聚系数分布函数P（C）表示从网络中任选一节点，其集）表示从网络中任选一节点，其集 聚系数值为聚系数值为C的概率的

10、概率式中式中，（x）为单位冲激函数。）为单位冲激函数。u聚度相关性聚度相关性 局部集聚系数局部集聚系数C（k）定义为度为）定义为度为k的节点的邻居之间存在的节点的邻居之间存在的平均边数的平均边数Mnn（k）与这些邻居之间存在的最大可能的）与这些邻居之间存在的最大可能的边数的比值，即边数的比值，即 局部集聚系数局部集聚系数C（k）与）与k的关系刻画了网络的聚度相关性的关系刻画了网络的聚度相关性介数和核度介数和核度 介数分为节点介数和边介数两种，反映了节点或边在整个介数分为节点介数和边介数两种，反映了节点或边在整个网络中的作用和影响力。网络中的作用和影响力。 节点的介数节点的介数Bi定义为定义为

11、边的介数边的介数Bij定义为定义为 介度相关性可以用介度相关性可以用B（k）k表示，它定义为所有度为表示，它定义为所有度为 k的节点的介数平均值随着的节点的介数平均值随着k的变化关系的变化关系。 节点介数分布节点介数分布Pv（B）定义为网络中节点介数为）定义为网络中节点介数为B的节点数的节点数占网络节点总数的比例占网络节点总数的比例。 边介数分布边介数分布Pe（B）定义为网络中边介数为）定义为网络中边介数为B的边数占网络的边数占网络总边数的比例。总边数的比例。核度核度 一个图的一个图的k核是指反复去掉度值小于核是指反复去掉度值小于k的节点及其连线后的节点及其连线后，所剩余的子图，该子图的节点数

12、就是该核的大小。，所剩余的子图，该子图的节点数就是该核的大小。 节点核度的最大值叫做网络的核度。节点核度的最大值叫做网络的核度。 节点节点的的核度可以说明节点在核中的深度，核度核度可以说明节点在核中的深度，核度的的最大值自然最大值自然就对应着网络结构中最中心的位置。就对应着网络结构中最中心的位置。度中心性度中心性u 度中心性分为节点度中心性分为节点度度中心性中心性和和网络网络度度中心性。中心性。节点节点vi的度中心性的度中心性CD（vi）定义为定义为 网络网络G的度中心性的度中心性CD定义定义为为介数中心性介数中心性u 介数介数中心性分为节点中心性分为节点介数介数中心性中心性和和网络网络介数介

13、数中心性。中心性。节点节点vi的介数中心性的介数中心性CB（vi）定义为）定义为网络网络G的介数中心性的介数中心性CB可简化为可简化为网络密度网络密度 网络密度指的是一个网络中各节点之间联络的紧密程度。网络密度指的是一个网络中各节点之间联络的紧密程度。网网络络 G的网络密度的网络密度d（G）定义为定义为 连通集团（子图）及其规模分布连通集团（子图）及其规模分布 连通集团（子图）就是指网络连通集团（子图）就是指网络G中的一个子图，在这个子图中的一个子图，在这个子图内，任意两个节点之间都至少存在一条简单路径。内，任意两个节点之间都至少存在一条简单路径。 把网络的各连通分支中阶数最大的一个称为最大连

14、通分支把网络的各连通分支中阶数最大的一个称为最大连通分支 连通图连通图G的连通程度通常叫做连通度。的连通程度通常叫做连通度。 点连通度定义为点连通度定义为u 边连通度定义为边连通度定义为 连通集团的规模分布反映了网络连通集团的规模分布反映了网络G中的各种规模的连通分支中的各种规模的连通分支的数目分布情况。实证研究表明，对于大量的的数目分布情况。实证研究表明，对于大量的无标度无标度网络，连网络，连通集团的规模也存在幂律分布。通集团的规模也存在幂律分布。例如，科学家合作网的连通子例如，科学家合作网的连通子图规模分布。图规模分布。有向网络的静态特征有向网络的静态特征u 入度分布和出度分布入度分布和出

15、度分布 平均入度平均入度kin和平均出度和平均出度kout为为 入度分布和出度分布分别记为入度分布和出度分布分别记为Pin（k）和）和Pout（k），分别），分别表示网络中任意取出一个节点，其入度值和出度值刚好为表示网络中任意取出一个节点，其入度值和出度值刚好为k的的概率。概率。 入（出）度分布与平均入（出）度之间具有如下关系式入（出）度分布与平均入（出）度之间具有如下关系式u 累积入度分布和累积出度分布累积入度分布和累积出度分布u 联合度分布联合度分布基于弧的方式：基于弧的方式：基于节点的方式基于节点的方式平均距离和效率平均距离和效率平均距离和效率平均距离和效率 由于有向网络里的弧是带有方向

16、的，所以从节点由于有向网络里的弧是带有方向的，所以从节点vi到到vj之间之间的距离的距离dij和从节点和从节点vj到到vi之间的距离之间的距离dji是不同的。距离是不同的。距离dij定定义为从节点义为从节点vi出发沿着同一方向到达节点出发沿着同一方向到达节点vj所要经历的弧的最所要经历的弧的最少数目，而它的倒数少数目，而它的倒数1dij称为从节点称为从节点vi到节点到节点vj的效率，记的效率，记为为ij。 有向连通简单网络的平均距离有向连通简单网络的平均距离L 因为效率可以用来描述非连通网络，所以可以定义有向网因为效率可以用来描述非连通网络，所以可以定义有向网络的效率络的效率LC为为介数介数

17、节点的介数节点的介数Bi定义定义为为 式中，式中，Njl表示从节点表示从节点vj到到vl的最短路径条数，的最短路径条数，Njl（i）表示）表示从节点从节点vj到到vl的最短路径的最短路径经经过节点过节点vi的条数。的条数。 边的介数边的介数Bij定义为定义为 式中，式中，Nlm表示从节点表示从节点vl到到vm的最短路径条数，的最短路径条数，Nlm（eij）表示从节点）表示从节点vl到到vm的最短路径经过边的最短路径经过边eij（方向相同）的（方向相同）的条数。条数。介数介数加权网络的静态特征加权网络的静态特征点权点权 节点节点vi的点权的点权Si定义为定义为 对于无向加权网络，点权对于无向加权网络，点权Si还可以用邻接矩阵元素表示为还可以用邻接矩阵元素表示为 对于有向加权网络对于有向加权网络可以定义入权和出权可以定义入权和出权单位权单位权介数分布和漏斗效应介数分布和漏斗效应 介数是用来衡量通过网络中某节点或某条边的最短路径的介数是用来衡量通过网络中某节点或某条边的最短路径的数目。在科学家网络中，