复杂网络的基本模型

1、复复 杂杂 网网 络络 的的 基基 本本 模模 型型刘伟刘伟青岛讨论班青岛讨论班 主要内容主要内容 1. 1. 复杂网络的分类复杂网络的分类 2. 2.描述网络结构的最基本的几个概念描述网络结构的最基本的几个概念 3. 3. 复杂网络的四个基本模型复杂网络的四个基本模型山东科技大学讨论班 1. 1. 复杂网络的分类复杂网络的分类 v 到目前为止，还没有给复杂网络下一个明确的定义还没有给复杂网络下一个明确的定义，只是从不同角度对复杂网络大致进行了分类。v 根据节点度的分布情况根据节点度的分布情况，可以将复杂网络分为指数网指数网络络和无尺度网络无尺度网络两大类。指数网络中的节点是同质的，它们的度大

2、致相同，绝大部节点的度都位于网络节点平均度附近，网络节点度分布随度数的增加呈指数衰减，使得网络中不存在度数特别大的节点。最经典的两种指数网络是Erds与Rnyi于1960年提出的ER随机图模型和Watt与Strogatz在1998年提出的WS小世界网络模型。山东科技大学讨论班 不同领域的复杂网络不同领域的复杂网络v 社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网v 生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络v 信息网络：WWW，专利使用，论文引用，计算机共享v 技术网络：电力网，Internet，电话线路网，v 交通运输网：航线网，铁路网，公路网，自然河流网山东

3、科技大学讨论班 Santa FeSanta Fe研究所的科学家合作网研究所的科学家合作网社会网络朋友关系网朋友关系网山东科技大学讨论班 生物网络生态网络生态网络蛋白质相互作用网络蛋白质相互作用网络神经网络神经网络食食物物链链山东科技大学讨论班 论文引用网论文引用网万维网万维网信息网络山东科技大学讨论班 技术网络InternetInternet电力网电力网山东科技大学讨论班 美国航空网美国航空网城市公共交通网城市公共交通网交通网络山东科技大学讨论班 从生成方式生成方式上可将复杂网络分成随机性网络随机性网络和确定性网确定性网络络。顾名思义，随机网络的生成是随机的，尽管生成规则相同，每次在电脑上模拟

4、生成的网络却存在差异性；确定性网络的生成规则是确定的，其结构特性可以精确求解。从边的方向性边的方向性上可将网络分为无向网络无向网络和有向网络有向网络，无向网络的边不存在方向性，有向网络的边却有方向。从边有无权值边有无权值可将网络分为加权网络加权网络和无权网络。无权网络。 从结构上，网络的分类还没有明确形成！从结构上，网络的分类还没有明确形成！山东科技大学讨论班 复杂网络的拓扑结构复杂网络的拓扑结构 网络网络是一个由多个节点组成的集合，节点是一个由多个节点组成的集合，节点之间有一定的连接。之间有一定的连接。例如： 国际互联网：节点-路由器 连接-光纤 科学论文引用网：节点-文章 连接-文章引用

5、社会网络：节点-个体人 连接-人际关系山东科技大学讨论班 2. 2. 描述网络结构的最基本的几个概念描述网络结构的最基本的几个概念度(degree)：朋友的个数朋友的个数节点 i 的度 ki 定义为与该节点连接的其他节点的数目。 直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）。网络中所有节点 i 的度 ki 的平均值称为网络的(节点)平均度，记为k. 网络中节点的度的分布用分布函数P(k)来描述， P(k)表示的是一个随机选定的节点的度恰好为 k 的概率，即一个网络中度为k的节点数的比例。例如：完全随机网络的度分布近似为例如：完全随机网络的度分布近似为Poiss

6、onPoisson分布分布度分布：山东科技大学讨论班 聚类系数（簇系数）（Clustering coefficient）：朋友的朋友还是不是朋友的情况朋友的朋友还是不是朋友的情况簇系数衡量的是网络的集团化程度 簇系数的概念对社会网络而言，集团化形态是其一个重要特征，集团表示网络中的朋友圈或熟人圈，集团中的成员往往相互熟悉，为衡量这种群集现象提出了簇系数的概念。山东科技大学讨论班 一般地，假设网络中的一个节点 i 有 ki 条边将它和其他节点相连，这 ki 个节点就称为节点 i的邻居。显然，在这 ki 个节点之间最多可能有 ki (ki -1)/2 条边。而这 ki 个节点之间实际存在的边数 E

7、i 和总的可能的边数 ki (ki -1)/2 之比就定义为节点 i 的聚类系数Ci ，即： 2/ ( (1)iiiiCEk k一个顶点的簇系数：一个顶点的簇系数：从几何特点看，上式的一个等价定义为：其中，与节点 i 相连的三元组是指包括节点 i 的的三个节点，并且至少存在从节点 i 到其他两个节点的两条边，如图：iiiiCi与点 相连的三角形的数量与点 相连的三元组的数量山东科技大学讨论班 显然，0C1。C=0当且仅当所有的节点均为孤立节点，即没有任何连接边；C=1当且仅当网络是全局耦合的，即网络中任意两个节点都直接相连。整个网络的簇系数：整个网络的簇系数：11niiCCn整个网络的聚类系数

8、C就是所有节点 i 的聚类 Ci 的平均值。对于一个含有N个节点的完全随机的网络，当N很大时，C=O(N-1) 许多大规模的实际网络都具有明显的聚类效应，它们的聚类系数尽管远小于1但却比O(N-1) 要大得多。事实上，在很多类型的网络(如社会关系网络)中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当N时，C=O(1)。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中“物以类聚，人以群分”的特性。山东科技大学讨论班 山东科技大学讨论班 最短路径（Shortest path）：两个顶点之间边数最少的路径两个顶点之间边数最少的路径 两点

9、之间的最短路径：两点之间的最短路径：从指定始点到指定终点的所有路径中长度最小的一条路径。从指定始点到指定终点的所有路径中长度最小的一条路径。 网络平均路径长度：网络平均路径长度：所有点对之间的最短路径的算术平均值。所有点对之间的最短路径的算术平均值。山东科技大学讨论班 山东科技大学讨论班 介数（介数（BetweennessBetweenness）：）：经过某个节点的最短路径的条数经过某个节点的最短路径的条数介数分为顶点介数和边介数两种，它是一个全局变量，反介数分为顶点介数和边介数两种，它是一个全局变量，反映了节点或边的作用和影响力。如果一对节点间共有映了节点或边的作用和影响力。如果一对节点间共

10、有B B条条不同的最短路径，其中有不同的最短路径，其中有b b条经过节点条经过节点i，那么节点，那么节点i i对这对对这对节点的介数的贡献为节点的介数的贡献为b/B/B。把节点。把节点i对所有节点对的贡献累对所有节点对的贡献累加起来再除以节点对总数，就可得到节点加起来再除以节点对总数，就可得到节点i的介数。类似的的介数。类似的，边的介数定义为所有节点对的最短路径中经过该边的数，边的介数定义为所有节点对的最短路径中经过该边的数量比例（量比例（关键点线！连通性影响关键点线！连通性影响？）。？）。 研究表明，节点的介数与度之间有很强的相关性，不同研究表明，节点的介数与度之间有很强的相关性，不同类型的

11、网络，其介数分布也大不一样。类型的网络，其介数分布也大不一样。山东科技大学讨论班 3. 3.复杂网络的四种基本模型复杂网络的四种基本模型四种拓扑结构四种拓扑结构规则网规则网随机网络模型随机网络模型小世界网络模型小世界网络模型无标度网络模型无标度网络模型山东科技大学讨论班 （1）规则网络）规则网络山东科技大学讨论班 山东科技大学讨论班 一般情况下，聚类系数较大，平均最短路径较长。山东科技大学讨论班 任意两点最短路径直接相连任意两点最短路径直接相连不经过任何点不经过任何点山东科技大学讨论班 随机网络模型随机网络模型山东科技大学讨论班 山东科技大学讨论班 山东科技大学讨论班 山东科技大学讨论班 小世

12、界模型小世界模型v 为了描述从一个局部有序系统到一个随机网络的转移过程，为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和和 Strogatz（WS）提出了一个新模型，通常称为小世界网提出了一个新模型，通常称为小世界网络模型。络模型。v WS模型始于一具有模型始于一具有N个节点最近邻近连接网络，然后每条边以概个节点最近邻近连接网络，然后每条边以概率率p重新连接。约束条件为节点间无重边，无自环。重新连接。约束条件为节点间无重边，无自环。山东科技大学讨论班 Watts-Strogatz小世界模型小世界模型 规则 小世界 随机P0P1随机性增强山东科技大学讨论班 vP=0 P=0.07

13、5 P=1v 当当p等于等于0时，对应于规则图。两个节点间的平均距离时，对应于规则图。两个节点间的平均距离线性地随线性地随N增长而增长，聚类系数大。最邻近连接网络具有高聚类特性。增长而增长，聚类系数大。最邻近连接网络具有高聚类特性。v 当当p等于等于1时，系统变为随机图。时，系统变为随机图。 对数地随对数地随N增长而增长，且集聚增长而增长，且集聚系数随系数随N增大而减少。随机图具有小的平均路径长度但没有高聚类特增大而减少。随机图具有小的平均路径长度但没有高聚类特性。性。v 在在p等于（等于（0，1）区间任意值时，）区间任意值时，约等于随机图的值，网络具有约等于随机图的值，网络具有小世界效应，即

14、二者兼备。小世界效应，即二者兼备。山东科技大学讨论班 山东科技大学讨论班 山东科技大学讨论班 山东科技大学讨论班 无标度(Scale-free)网络山东科技大学讨论班 Scale-free网络的特性网络的特性v 度分布呈幂率分布度分布呈幂率分布v 中枢节点出现中枢节点出现v 鲁棒性鲁棒性v 脆弱性脆弱性山东科技大学讨论班 kkp )(山东科技大学讨论班 山东科技大学讨论班 v 无标度模型由无标度模型由Albert-Lszl Barabsi和和Rka Albert在在1999年首先提出，年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制：现实网络的无标度特性源于众多网络所共有的两种

15、生成机制：v （）网络通过增添新节点而连续扩张；）网络通过增添新节点而连续扩张；v （）新节点择优连接到具有大量连接的节点上。）新节点择优连接到具有大量连接的节点上。v 增长和择优连接这两种要素激励了增长和择优连接这两种要素激励了BarabsiAlbert模型的提出，该模型的提出，该模型首次导出度分布按幂函数规律变化的网络。模型首次导出度分布按幂函数规律变化的网络。v 模型的算法如下：模型的算法如下：v （1）增长：开始于较少的节点数量（）增长：开始于较少的节点数量（m0），），在每个时间间隔增添一在每个时间间隔增添一个具有个具有m（m0）条边的新节点，连接这个新节点到条边的新节点，连接这个新

16、节点到m个不同的已经个不同的已经存在于系统中的节点上。存在于系统中的节点上。v （2）择优连接：在选择新节点的连接点时，假设新节点连接到节点）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率的概率取决于节点取决于节点i的度数即的度数即jjiikkk)(山东科技大学讨论班 v 经过经过t时间间隔后，该算法程序产生一具有时间间隔后，该算法程序产生一具有N=t+m0个节点，个节点，mt条边条边的网络。的网络。v 数量模拟表明具有数量模拟表明具有k条边的节点的概率服从指数为条边的节点的概率服从指数为r=3的幂指数分布。的幂指数分布。v 模型的度分布是与时间无关的渐进分布且与系统规模无关。

17、模型的度分布是与时间无关的渐进分布且与系统规模无关。 v 幂律度分布的系数与幂律度分布的系数与 成正比成正比 。v 无标度模型的动态特性可以用各种分析方法给出无标度模型的动态特性可以用各种分析方法给出 ：v 平均场理论平均场理论v 主方程法主方程法v 变化率方程法变化率方程法 2m山东科技大学讨论班 v 幂幂律律分布函数的无标度性质：考虑一个概率分布函数分布函数的无标度性质：考虑一个概率分布函数f(x)，如果对任如果对任意给定常数意给定常数a，存在常数存在常数 b 使得函数使得函数 f(x) 满足如下满足如下“无标度条件无标度条件”:v 幂幂律律分布也称这无标度分布也称这无标度(scale-free)分布，具有幂律度分布的网络分布，具有幂律度分布的网络也称为无标度网络，这是由于幂律分布函数具有如下无标度性质。也称为无标度网络，这是由于幂律分布函数具有如下无标度性质。 5)-(1 xbfaxfv 那么必有那么必有(假定假定 ） 011ff 6)-(1 ) 1 () 1 (,)