无标度网络模型

article/2025/8/30 18:22:12

网络节点的度没有明显的特征长度我们就称之为无标度网络。

一、BA无标度网络模型

1、模型概述

ER随机图和WS小世界模型忽略了实际网络的两个重要特性:
(1)增长特性:即网络的规模是不断扩大的。例如每个月都会有大量的新的科研文章发表,www上则每天都有大量新的网页产生。而ER随机图和WS小世界模型中网络节点数是固定的。
(2)公先连接特性:即新的节点更倾向于与那些具有较高连接度的hub节点相连接。这种现象也称为“富者更富”或“马太效应”。 例如,新发表的文章更倾向于引用一些已被广泛引用的重要文献,新的个人主页上的超文本链接更有可能指向有影响的站点。而在ER随机图中,两个节点之间是否有边相连是完全随机确定的,在WS小世界模型中,长程边的端点也是完全随机确定的。
基于上述增长和优先连接特性,前人们又提出了BA无标度网络模型,构造算法如下:
(1)增长:从一个具有m 0 _0 0个节点的连通网络开始,每次引入一个新的节点并且连到m个已存在的节点上,这里m<=m 0 _0 0
(2)优先连接:一个新节点与一个已经存在的节点i相连接的概率与节点i的度k i _i i之间有如下关系:
在这里插入图片描述
在经过t步后,BA算法产生一个包含N=t+m 0 _0 0个节点和mt +M 0 _0 0条边的网络,其中M 0 _0 0是初始时刻t=0的m 0 _0 0 个节点之间存在的边数。
下图显示了参数为m 0 _0 0=M 0 _0 0=3、m=2的BA网络的演化过程。已有节点用实心圆点表示,实心圆点的相对大小对应于节点度的相对大小。每次新增加的一个节点用空心圆点表示,它按优先连接机制与网络中已有的两个节点相连。
在这里插入图片描述

2、幂律度分布

BA模型具有幂律度分布且与参数、网络规模N均无关。
对BA模型的度分布的理论分析可以有多种方法,包括主方程方法、率方程方法和更为简洁的近似方法即平均场理论。 在复杂网络分析中,这几种方法得到的渐近结果往往都是相同的。

2.1 平均场理论

假设初始网络有m 0 _0 0个节点,并记时刻t节点i的度为k i _i i(t)。对充分大的t,可忽略初始网络中的M 0 _0 0条边并有m 0 _0 0+t ≈ \approx t。当一个新节点加入到系统中来时,节点i的度改变(即增加1)的概率为:
在这里插入图片描述
现在用平均场理论对BA模型的度分布做近似分析,为此需要给出如下的连续化假设:
(1)时间t不再是离散的,而是连续的;
(2)节点的度值也不再是整数,而是可以为任意实数。
在这两个假设下,上式概率公式可以解释为节点i的度的变化率,从而可以把网络演化近似转化为单个节点演化的平均场方程:
在这里插入图片描述
假设节点i是在时刻t i _i i加入网络的,那么上面微分方程的初始条件为k(t i _i i)=m。于是求得:
在这里插入图片描述
假设当时间t-> ∞ \infty 时,度分布P(k(t))收敛于稳态度分布P(k)。由概率定义有:
在这里插入图片描述
可得:
在这里插入图片描述
假设是以相等的时间间隔添加节点的,那么t i _i i的概率密度为:
在这里插入图片描述
从而有:
在这里插入图片描述
可得:
在这里插入图片描述
在这里插入图片描述
上式表明,P(k)/2m 2 ^2 2的取值与m无关。总是近似为k − 3 ^{-3} 3

2.2 主方程方法

平均场分析毕竟是一种近似分析方法,得到的度分布的幂指数是正确的,但是度分布的系数并不准确。下面我们将针对更为一般的模型基于主方程方法给出的精确计算。
BA网络平均路径长度和聚类系数的推导由于涉及较深的数学知识,这里只给出有关结果。BA网络的平均路径长度比网络规模的对数还要小;具体地说,当m≥2时有:
在这里插入图片描述
另一方面,当网络规模充分大时,BA网络并不具有明显的聚类特征;具体地说,BA网络的聚类系数满足:
在这里插入图片描述

二、Price模型

1、模型描述

BA模型的度分布是幂指数固定为3的幂律分布,而许多实际的无标度网络的度分布的幂指数都是在2与3之间的。因此,我们希望能有一个幂指数可以在一定范围内调整的无标度网络模型。而这种模型居然在BA模型提出之前的30年就已经存在了。它就是Price模型。
Price有向网络模型构造算法:
(1)增长:从一个具有m 0 _0 0个孤立节点的网络开始,每次引入一个新的节点并且通过m条有向边指向m个已存在的节点上,这里m<=m 0 _0 0
(2)累积优势:一个新节点有边指向一个已经存在的入度为k i i n ^{in}_i iin的节点i的概率满足如下关系:
在这里插入图片描述

2、幂指数可调的入度分布

在这里插入图片描述
在这里插入图片描述
其中在这里插入图片描述

幂指数为:
在这里插入图片描述
当k i n ^{in} in>>a时有:
在这里插入图片描述
这表明Price网络模型的入度分布近似服从幂指数 λ \lambda λ=2 +a/m的幂律分布。如果a/m≤1,那么幂指数 λ \lambda λ∈(2,3],这意味着Price网络模型是一个非均匀的异质网络。随着a/m值的增加,Price网络模型的人度分布的均匀性也不断增加。因此,Price网络模型实际上是一个幕指数可调的幂律人度分布的网络模型。

3、幂指数可调的无向无标度网络

如果把Price模型中的每一条有向边都视为无向边,那么这样构成的无向网络中的节点i的度k i _i i与Price 模型中的节点i的出度m和人度k i i n _i^{in} iin 之间具有如下关系:k i _i i=k i i n _i^{in} iin +m。因此,基于Price模型的入度分布对应的无向网络的度分布为:
在这里插入图片描述
这样就得到了幂指数在(2, ∞ \infty )范围内可调的具有幂律度分布的无向网络。
BA模型可以视为Price模型在取m=a时的特例。

4、优先连接机制的计算机实现

Price模型的计算机实现算法:
(1)给定一个具有m 0 _0 0个节点的初始强连通网络。把每一条边所指向的节点的编号添加到数组Array中。
(2)给定参数p ∈ \in [0,1]。对于t=1,2,,,N-m 0 _0 0,执行如下操作:
1)生成一个完全随机数r ∈ \in [0,1);
2)如果r<p,那么就完全随机的在数组Array中选择一个元素。
3)如果r>=p,那么就完全随机的选择一个节点。
4)执行步骤1)到3)m次后,添加从新加入节点指向选定的m个节点的m条有向边,并把这m个节点的编号添加到数组Array中。

5、节点复制模型

在优先连接的计算机实现中,由于数组Array是由网络中每个节点所指向的邻居节点的编号组成的,因此完全随机地在数组Array中选取一个元素等价于如下操作:完全随机地选择一个已有节点,然后再完全随机地选择该节点所指向的一个邻居点。
也就是说,在一定程度上(由参数p决定),新加入节点倾向于模仿(复制)网络中已有节点的行为。这种节点复制模式导致“富者更富”:某个节点如果已经受到很多关注,那么今后就更有可能受到更多的关注。我们可以把参数p视为复制概率:p值越大,意味着新加入的节点越倾向于复制已有节点的行为,从而导致更为显著的富者更富。
节点复制模型构造算法如下:
(1)增长:从一个具有m 0 _0 0个孤立节点的网络开始,每次引入一个新的节点并且通过m条有向边指向m个已存在的节点上,这里m≤m 0 _0 0
(2)节点复制:给定一个参数p∈[0,1],按照如下方式选择已有节点,并添加从新节点指向该已有节点的有向边:
1)生成一个完全随机数r ∈ \in [0,1);
2)如果r<p,那么就完全随机的选择一个节点,然后再完全随机的选取该节点所指向的一个邻居节点。
3)如果r>=p,那么就完全随机的选择一个节点。
4)执行步骤1)到3)m次,并避免重复选择节点。

三、无标度网络模型的推广

BA模型把实际复杂网络的无标度特性归结为增长和优先连接这两个非常简单明了的机制,这很好地体现了科学研究中的从复杂现象提取简单本质的特点。但是在BA模型中,越老的节点具有越高的度;换句话说,后来者不可能居上。然而,在许多实际网络中,节点的度及其增长速度并非只与该节点的年龄有关,还与节点的内在属性相关。
接下来介绍BA模型的两种推广:一种是考虑到节点之间具有不同的竞争能力的适应度模型,另一种是基于局域世界优先连接的网络模型。

1、适应度模型

适应度模型构造算法:
(1)增长:从一个具有m 0 _0 0个节点的连通网络开始,每次引入一个新的节点并且连到m个已存在的节点上,这里m≤m 0 _0 0
(2)优先连接:一个新节点与一个已经存在的节点i相连接的概率与节点i的度k i _i i和适应度η i _i i之间满足如下关系:
在这里插入图片描述
可以看出,适应度模型与BA无标度模型的区别在于,适应度模型中的优先连接概率与节点的度和适应度之积成正比,而不是仅与节点的度成正比。

2、局部世界演化网络模型

局部世界演化模型是在BA模型的基础上基于在诸多实际的复杂网络中存在着局域世界考虑的。
局域世界演化模型构造算法:
(1)增长:网络初始时有m 0 _0 0个节点和e 0 _0 0条边。每次新加人一个节点和附带的m条边。
(2)局域世界优先连接:随机地从网络已有的节点中选取M个节点(M≥m),作为新加入节点的局域世界(LW)。新加入的节点根据优先连接概率来选择与局域世界中的m个节点相连,其中LW由新选的M个节点组成:
在这里插入图片描述
在每一时刻,新加入的节点从局域世界中按照优先连接原则选取m个节点来连接,而不是像BA无标度模型那样从整个网络中来选择。构造一个节点的局域世界的法则根据实际的局域连接而不同,上述模型中只考虑了随机选择的简单情形。
显而易见,在t时刻,m≤M≤m 0 _0 0+t,因此,上述局域世界演化网络模型有两个特殊情形:M=m和M=t+m 0 _0 0
(1)特殊情形1:M=m
这时,新加入的节点与其局域世界中所有的节点相连接,这意味着在网络增长过程中,优先连接原则实际上已经不发挥作用了。这等价于BA无标度网络模型中只保留增长机制而没有优先连接时的特例。此时,第i个节点的度的变化率为
在这里插入图片描述
网络度分布服从指数分布:
在这里插入图片描述
(2)特殊情形2:M=t+m 0 _0 0
在这种特殊情形,每个节点的局域世界其实就是整个网络。因此,局域世界模型此时完全等价于BA无标度网络模型。

四、鲁棒性与脆弱性

对于给定的一个网络,每次从该网络中移走一个节点,也就同时移走了与该节点相连的所有的边,从而有可能使得网络中其他节点之间的一些路径中断。如果在节点i和节点j之间有多条路径,中断其中的一些路径就可能会使这两个节点之间的距离d i j _{ij} ij增大,从而整个网络的平均路径长度L也会增大。如果节点i和j之间的所有路径都被中断,那么这两个节点之间就不再连通了。如果在移走少量节点后网络中的绝大部分节点仍是连通的,那么就称该网络的连通性对节点故障具有鲁棒性。
考虑两类节点去除策略:一是随机故障策略,即完全随机地去除网络中的一部分节点;二是蓄意攻击策略,即从去除网络中度最高的节点开始,有意识地去除网络中一部分度最高的节点。
在这里插入图片描述
在这里插入图片描述
从上图得知无标度网络对随机节点故障具有极高的鲁棒性;但对蓄意攻击具有极高的脆弱性,只要有意识的去除网络中极少量度大的节点就会对整个网络的连通性产生很大的影响。
在这里插入图片描述
上图形象的比较了随机网络和无标度网络的鲁棒性。


http://chatgpt.dhexx.cn/article/ThmFNwXO.shtml

相关文章

2019年互联网公司月饼哪家强?阿里、百度、网易等14家中秋月饼盘点

一年一度的中秋节日马上到来&#xff0c;"八月十五月儿圆&#xff0c;中秋月饼香又甜"&#xff0c;没有月饼的中秋节是不完整的。而在互联网公司&#xff0c;月饼已然成为福利和文化的象征。特别是一些互联网大厂&#xff0c;在月饼设计上特别用心。今天&#xff0c;…

黑芝麻智能与上汽通用五菱签署战略合作协议;亚马逊广告发布一系列全新广告解决方案 | 全球TMT...

国内市场 黑芝麻智能与上汽通用五菱签署战略合作协议。双方在车规级自动驾驶计算芯片、视觉感知算法等方面展开紧密合作。上汽通用五菱和黑芝麻智能将基于华山二号A1000系列自动驾驶计算芯片、FAD全自动驾驶平台、山海人工智能开发平台等一系列开发工具&#xff0c;结合黑芝麻智…

如何处理投递的邮件被趋势RBL拦截的问题

外发邮件时&#xff0c;对方未收到&#xff0c;查询日志&#xff0c;报错如下&#xff1a; ……..blocked_using_Trend_Micro_RBL._Please_see…… 亚信安全使用的垃圾邮件地址库为国际的MAPS库&#xff0c;您可以通过&#xff1a;https://www.ers.trendmicro.com/ 右侧的IP Re…

持续保持逆势增长,亚信科技带给我们哪些启示?

面对逆境仍然能够持续保持业绩稳步增长&#xff0c;亚信科技可以带给我们哪些启示和借鉴&#xff1f; 逆势增长的亚信科技 众所周知&#xff0c;由于三年疫情带来的巨大冲击以及各种“黑天鹅”事件频发&#xff0c;近年来许多企业的财务报表都乏善可陈。 然而就是在这样复杂的外…

从雅虎被黑事件看在线数据的保护

根据最近雅虎被黑事件我们都能了解些什么&#xff1f;10 大最常见密码&#xff0c;其中“123456”终于胜过了 2011 年人民群众最喜爱的密码冠军“password”&#xff0c;而按照键盘上字母排列顺序的“qwert”也再次入围。 当您注册网站服务时&#xff0c;是否也会使用常见的单…

JVM——垃圾回收算法

1. 概述 垃圾收集&#xff0c;不是Java语言的伴生产物。早在1960年&#xff0c;第一门开始使用内存动态分配和垃圾收集技术的Lisp语言诞生。 关于垃圾收集有三个经典问题&#xff1a; 哪些内存需要回收&#xff1f; 什么时候回收&#xff1f; 如何回收&#xff1f; 1.1. 面…

安全世界 5正当时:亚信安全2020第五空间战略发展高峰论坛举行

点击上方关注我们! 11月15日&#xff0c;由亚信安全主办的“安全世界 5正当时”2020第五空间战略发展高峰论坛在北京盛大举行。来自政府、运营商、金融和能源等关键信息基础设施行业的负责人&#xff0c;生态合作伙伴出席本次活动&#xff0c;“共启安全数字世界”&#xff0c;…

趋势科技年度巨献 《2020》反黑大片

《2020》是趋势科技根据 ICSPA 的「2020 项目」报告所改编成的影片,描述一个不久即将发生的未来世界。这些影片以虚构的故事呈现该报告当中所描绘的社会变迁与科技演进,我们将告诉您移动及云安全技术的演进如何影响人与人之间以及人与世界的互动,还有人们如何工作以及如何认…

亚信安全走过“融合、突破”元年 探索网络安全的未来

2016年12月16日&#xff0c;云与大数据安全技术厂商亚信安全在京召开“亚信安全1周年暨2017战略媒体沟通会”。本次会议指明了不断演化的全球网络威胁及国家网络安全战略驱动下的产业发展源动力&#xff0c;回顾总结了亚信安全在2016年成立元年对核心竞争力塑造的融合之力&…

摆脱科技僵尸,回归生龙活虎

你身旁有这样无法抗拒尝试新科技的家人吗?半夜不睡觉,守着闪烁蓝光的手机、平板和其他夜猫子一起按赞、分享、留言和发短信。如果这听起来很像你或你的家人&#xff0c;这里有简单四步计划来帮助你减少科技消耗。 1.在你准备拥抱枕头前的3到4小时,停止所有的网络活动 英国睡眠…

亚信安全走过“融合、突破”元年 透露人工智能创新技术战略

近日&#xff0c;亚信安全在京召开“亚信安全1周年暨2017战略媒体沟通会”。本次会议指明了不断演化的全球网络威胁及国家网络安全战略驱动下的产业发展源动力&#xff0c;回顾总结了亚信安全在2016年成立元年对核心竞争力塑造的融合之力&#xff0c;突破之道。同时&#xff0c…

趋势科技4月移动客户端病毒报告

2014年4月移动客户端安全威胁概况 截至2014年4月30日,中国区移动客户端病毒码1.669.60,大小9,792,484字节,可以检测病毒约221万个。移动客户端病毒约12万个。 趋势科技移动客户端病毒码中排名前十的病毒家族: 趋势科技移动客户端4月新增病毒码中排名前十的病毒家族: 趋势…

中国互联网二十四年红黑史

作者 | 刘煜 转自一点财经 总有一种互联网时代到达拐角的感觉。 但不知道是到底是因为自身敏感&#xff0c;还是狼来了的条件反射&#xff0c;我们对未来&#xff0c;总是会突然欣喜之后又毫不在乎。 直播答题分钱与区块链和 P2P 没有接得住关于互联网继续狂欢的愿望&#xff0…

迎战APT 亚信安全发布高级威胁治理XDR战略

从网络病毒泛滥到APT攻击持续升级&#xff0c;从黑客刷存在感&#xff0c;到导致用户数据资产大量泄露的黑产兴起&#xff0c;APT&#xff08;高级持续性威胁&#xff09;堪称是在网络空间里进行的军事对抗。攻击者会长期持续地对特定目标进行精准打击。就像你家里隐藏了一个小…

中国四大骨干网和三大运营商网络是什么关系?

中国四大骨干网和三大运营商网络是什么关系&#xff1f; 文章目录 介绍Q1: 中国四大骨干网是什么&#xff1f;Q2: 和三大网运营商的关系是什么呢&#xff1f;Q3&#xff1a; 另外3个对个人用户开放使用吗&#xff1f;如何盈利&#xff1f; 中国四大骨干网络1、 中国科技网&…

亚信Internet中国

&#xff08;亚信创始人田溯宁&#xff09; 本文写于1999年。 现阶段&#xff0c;中国Internet上的商业价值远没有想象的那么大&#xff0c;所以&#xff0c;在中国率先成功的Internet企业是亚信这样从事Internet基础建设的公司。 美国也一样&#xff0c;最成功的Internet企业是…

你的邮件为何被标记为垃圾邮件?

虽然现在垃圾邮件(SPAM)可能不是最致命的威胁,但它仍然是大家每天都要面对的严重困扰,比如趋势科技的用户每月就要处理数十亿封的垃圾邮件。垃圾邮件不仅骚扰用户,更经常通过附件或恶意链接来散播恶意软件。 处理垃圾邮件最有力的手段之一就是IP信誉评比技术,它会检查电子…

【金猿产品展】亚信科技“数据探索分析平台”——深挖数据价值,助客户高效管理和经营生产...

亚信科技产品 本产品由亚信科技投递并参与“数据猿年度金猿策划活动——2020大数据产业创新服务产品榜单及奖项”评选。 大数据产业创新服务媒体 ——聚焦数据 改变商业 亚信科技数据探索分析平台AISWare DataDiscovery旨在打造敏捷开放的数据探索与可视化分析工具&#xff0c…

确认过眼神,这就是亚信科技的核心能力

6月28日&#xff0c;上海&#xff0c;一年一度的MWC&#xff08;世界移动大会&#xff09;&#xff0c;赴亚信科技之约&#xff01; 这已经是亚信科技连续第二年参加在上海举行的MWC。在移动通信领域&#xff0c;未来的趋势从未像今天这样清晰&#xff1a;5G、人工智能等技术的…

【金猿案例展】亚信科技——某省公路联网中心大数据平台建设

亚信科技案例 本案例由亚信科技投递并参与“数据猿年度金猿策划活动——2020大数据产业创新服务企业榜单及奖项”评选。 大数据产业创新服务媒体 ——聚焦数据 改变商业 2019年5月&#xff0c;国务院办公厅印发《深化收费公路制度改革取消高速公路省界收费站实施方案》&#x…