历华毛子种枝大学 第三讲:复杂网络结构模型 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) 小世界网络 增加随机性 随机加边