西安电子科技大学：《复杂网络与群体智能》课程教学课件（研究生）第三讲 复杂网络的结构特征

历华毛子种枝大学 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY (1)随机网络模型 (2)小世界网络 (3)无标度网络 (4)社区网络 2

（1）随机网络模型 （2）小世界网络 （3）无标度网络 （4）社区网络 第三讲：复杂网络结构模型 2

历些毛子代枝大学 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY >随机图模型： 匈牙利数学家Edos和Renyis建立的随机图模型，简称ER模型， 假设网络节点之间是否有连边是随机的，是以概率来决定的。 用随机图模型来生成网络的做法很简单：给定网络节点个数W ，然后以概率决定任意两点之间是否有连边。 (a) =0 (b) p=0.05 (c) p=0.1 (d) p=0.2 图.30节点的随机图：(a)p=0,(b)p=0.05,(c)p-0.1;(d)p=0.2。 3

第三讲：复杂网络结构模型 3 随机图模型： • 匈牙利数学家Edös和 Rényi建立的随机图模型，简称ER模型， 假设网络节点之间是否有连边是随机的，是以概率来决定的。 用随机图模型来生成网络的做法很简单：给定网络节点个数N ，然后以概率p决定任意两点之间是否有连边。 图. 30节点的随机图：(a) p=0; (b) p=0.05; (c) p=0.1; (d) p=0.2

历安毛子代枚大等 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY >随机图模型的结构特征： 平均度<>：<>=pN-1)pW 网络密度：ER随机图中边的总数为M=Wp(N-1)/2,可能的最多边数为 N(N-1)/2,因此，网络密度为D=p。 聚集系数CC:在ER随机图模型中，任意两个节点相连的概率都是p, 也就是说CC=p。而在大规模网络中p远远小于1，也就是说ER随机图 不具有聚集特性。 (a) p=0 (b) p=0.05 (c) p=0.1 (d) p=0.2 图.30节点的随机图：(a)p=0,(b)p-0.05;(c)p-0.1;(d)p=0.2

第三讲：复杂网络结构模型 4 随机图模型的结构特征： • 平均度：=p(N-1)≈pN • 网络密度：ER随机图中边的总数为M=Np(N-1)/2, 可能的最多边数为 N(N-1)/2，因此，网络密度为D=p。 • 聚集系数CC：在ER随机图模型中，任意两个节点相连的概率都是p, 也就是说CC=p。而在大规模网络中p远远小于1，也就是说ER随机图 不具有聚集特性。 图. 30节点的随机图：(a) p=0; (b) p=0.05; (c) p=0.1; (d) p=0.2

历些毛子代枝大学 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY >随机图模型的结构特征： 平均路径长度L取：可以做一个近似的估算，任取一个点，和它距离为1 的节点数有2个，.，距离为L的节点数 有LR个，见表2-1。表2-1中右列中各项之和为N,有理由相信 N∝LER,即 InN InN LER I In pN 距离 节点数量 0 1 1 2 2 。 LER LER 5

第三讲：复杂网络结构模型 5 随机图模型的结构特征： • 平均路径长度LER：可以做一个近似的估算，任取一个点，和它距离为1 的节点数有个，距离为2的节点数有 2个，.，距离为LER的节点数 有𝐿𝐸𝑅个，见表2-1。表2-1中右列中各项之和为N，有理由相信 N∝𝐿𝐸𝑅 , 即 距离 节点数量 0 1 1 2 2 . . LER 𝐿𝐸𝑅 . . 𝐿𝐸𝑅 ∝ 𝑙𝑛𝑁 𝑙𝑛 = 𝑙𝑛𝑁 𝑙𝑛

历安毛子代枚大学 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY >随机图模型的结构特征： ·度分布：在网络规模比较小时W20),就可认为随机图度分布 20 服从泊淞分布。 100 (飞：=k)= Ak e 10 20 6

第三讲：复杂网络结构模型 6 随机图模型的结构特征： • 度分布：在网络规模比较小时(N<20)，任意给定一个节点vi，其度ki为k 的概率服从二项分布，即。 𝑃 𝑘𝑖 = 𝑘 = 𝑁 𝑘 𝑝 𝑘 1 − 𝑝 𝑁−𝑘 = 𝑁! 𝑘! 𝑁−𝑘 ! 𝑝 𝑘 1 − 𝑝 𝑁−𝑘 (𝑘𝑖 = 𝑘) = λ 𝑘 𝑘! 𝑒 −λ 当网络规模逐渐增大时，二项分布趋近于泊 淞分布，其中λ=Np。一般的，当网络规模 大于等于20(N≥20), 就可认为随机图度分布 服从泊淞分布。 0 10 20 30 0 100 200 300 400 500 600 k 对应度k处节点的数量 (a)

历些毛子代枝大兽 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY >WS小世界网络模型 现实网络的小世界特性。 现实世界大多数网络尽管规模很大，但是任意两个节（顶）点间却 有一条相当短的路径的事实。以日常语言来说，它反映的是相互连 边的数目可以很少（边密度较低），但平均路径长度却很短。 ·举例：社会网络。 ·小世界网络：是一类网络的统称，这类网络平均路径较短，聚集系 数较高

第三讲：复杂网络结构模型 7 WS小世界网络模型 现实网络的小世界特性。 现实世界大多数网络尽管规模很大，但是任意两个节（顶）点间却 有一条相当短的路径的事实。以日常语言来说，它反映的是相互连 边的数目可以很少（边密度较低），但平均路径长度却很短。 • 举例：社会网络。 • 小世界网络：是一类网络的统称，这类网络平均路径较短，聚集系 数较高

历安毛子代枚大等 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY WS小世界网络模型。 1998年，Watts和Strogatz提出了小世界网络这一概念，并建立 了WS模型。 第一步：从规则图开始，考虑一个含有N个点的最近邻耦合网络，它们 围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶 数。 第二步：随机化重连，以概率随机地从新连接网络中的每个边，即将 边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点 。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个 节点都不能有边与自身相连

• 第一，小世界特性。 大多数网络尽管规模很大，但是任意两个节（顶）点间却有一条 相当短的路径的事实。以日常语言来说，它反映的是相互连边的 数目可以很少（边密度较低），但平均路径长度却很短。 • 举例：环形规则网络， 小世界网络 • 小世界网络：是一类网络的统称，这类网络平均路径较短，聚集 系数较高。 • WS小世界网络模型。 1998年, Watts和Strogatz提出了小世界网络这一概念,并建立 了WS模型。 第一步：从规则图开始，考虑一个含有N个点的最近邻耦合网络，它们 围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶 数。 第二步：随机化重连，以概率p随机地从新连接网络中的每个边，即将 边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点 。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个 节点都不能有边与自身相连。 第三讲：复杂网络结构模型

历些毛子科枚大” 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY WS小世界网络模型。 WS小世界模型可以在重连概率p=0到p=1之间灵活的构建网络。p=0是完全的 规则网络，p=1是完全的随机网络，0>K>>inW>>1。K~>inN能保证网络是联通的，N>>K保证网络具有 稀疏性，inN>>1保证网络有一定的规模

• 第一，小世界特性。 大多数网络尽管规模很大，但是任意两个节（顶）点间却有一条 相当短的路径的事实。以日常语言来说，它反映的是相互连边的 数目可以很少（边密度较低），但平均路径长度却很短。 • 举例：环形规则网络， 小世界网络 • 小世界网络：是一类网络的统称，这类网络平均路径较短，聚集 系数较高。 • WS小世界网络模型。 WS小世界模型可以在重连概率p=0到p=1之间灵活的构建网络。p=0是完全的 规则网络，p=1是完全的随机网络，0>K>>linN>>1。K>>linN能保证网络是联通的，N>>K保证网络具有 稀疏性，linN>>1保证网络有一定的规模。 第三讲：复杂网络结构模型 (a) 规则网络 (b) 小世界网络 (c) 随机网络 p=0 增加随机性 随机重连

历安毛子代枚大学 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY NW小世界网络模型。 WS小世界模型的问题在于当网络密度较小（较小）时，边重连可能导致 网络不联通。 NW小世界网络模型。1999年，Newman和Watts提出了另一种比较常用的小 世界模型，称为NW小世界网络模型，其基本步骤如下： 步骤1：产生一个环形的规则近邻连接网络，网络有个节点，每个节点和 近邻的k个节点相连： 步骤2：在任意两个节点之间以概率随机加边。 NW小世界网络模碧V小世网销蒸型的S真步骤2，NW模型是随 (a）规则网络 机重连，边的总 边的总数是增加的。 随机加边 增加随机性

• 第一，小世界特性。 大多数网络尽管规模很大，但是任意两个节（顶）点间却有一条 相当短的路径的事实。以日常语言来说，它反映的是相互连边的 数目可以很少（边密度较低），但平均路径长度却很短。 • 举例：环形规则网络， 小世界网络 • 小世界网络：是一类网络的统称，这类网络平均路径较短，聚集 系数较高。 • NW小世界网络模型。 WS小世界模型的问题在于当网络密度较小（K较小）时，边重连可能导致 网络不联通。 NW小世界网络模型。1999年，Newman和Watts提出了另一种比较常用的小 世界模型，称为NW小世界网络模型，其基本步骤如下： 步骤1：产生一个环形的规则近邻连接网络，网络有N个节点，每个节点和 近邻的k个节点相连； 步骤2：在任意两个节点之间以概率p随机加边。 NW小世界网络模型和WS小世界网络模型的区别在于步骤2，NW模型是随 机重连，边的总数不会增加，而NW模型是随机加边，边的总数是增加的。 第三讲：复杂网络结构模型 (a) 规则网络 (b) 小世界网络 (c) 小世界网络 增加随机性 随机加边

面些毛子种枝大学 第三讲：复杂网络结构模型 XIDIAN UNIVERSITY ·NW小世界网络模型。 NW小世界网络模型。1999年，Newman和Wats提出了另一种比较常用的小 世界模型，称为NW小世界网络模型，其基本步骤如下： 步骤1：产生一个环形的规则近邻连接网络，网络有个节点，每个节点和 近邻的k个节点相连； 步骤2：在任意两个节点之间以概率随机加边。 NW小世界网络模型和WS小世界网络模型的区别在于步骤2，NW模型是随 机重连，边的总数不会增加，而NW模型是随机加边，边的总数是增加的。 (a)规则网络 (b)小世界网络 (c)小世界网络 随机加边 增加随机性

• 第一，小世界特性。 大多数网络尽管规模很大，但是任意两个节（顶）点间却有一条 相当短的路径的事实。以日常语言来说，它反映的是相互连边的 数目可以很少（边密度较低），但平均路径长度却很短。 • 举例：环形规则网络， 小世界网络 • 小世界网络：是一类网络的统称，这类网络平均路径较短，聚集 系数较高。 • NW小世界网络模型。 NW小世界网络模型。1999年，Newman和Watts提出了另一种比较常用的小 世界模型，称为NW小世界网络模型，其基本步骤如下： 步骤1：产生一个环形的规则近邻连接网络，网络有N个节点，每个节点和 近邻的k个节点相连； 步骤2：在任意两个节点之间以概率p随机加边。 NW小世界网络模型和WS小世界网络模型的区别在于步骤2，NW模型是随 机重连，边的总数不会增加，而NW模型是随机加边，边的总数是增加的。 第三讲：复杂网络结构模型 (a) 规则网络 (b) 小世界网络 (c) 小世界网络 增加随机性 随机加边