基金项目:国家自然科学基金(60974082)
通讯作者:李 彬(1985-),男,山西永济人,硕士研究生,主要从事复杂网络理论的研究工作.
(College of Sciences,Xidian University, Xi'an 710071, China)Xi'an University of Arts and Science, Xi'an 710065,Chinak)
由于对复杂网络的拓扑结构知之甚少,其抗毁性测度的研究一直是个比较困难的问题。从网络连通性的角度出发,在随机失效率的前提下对网络的抗毁性测度进行定义。并分别在只有选择性攻击和随机性攻击的情况下验证所提的全网连通度的有效性,进一步对无标度网络和随机网络的抗毁性能进行比较和分析。结果 表明考虑了随机失效率的网络抗毁度定义更加确切有效。
School physical education is an important component of school education, its primary purpose is to promote students' physical and mental development, and to extend the meaning of school education. School sport is a complete system.It is rich in content, and it has a wide variety of forms.It not only reflects the thoughts and concepts of educators, but also reflects the educational philosophy of the school. Through extensive literature research profound, interpretation about School Education Physical ideology of Quzonghu has been made, especially the development of School Physical Education on the reform of the 21st century school PE, domestic and foreign comparison of school PE. Great achievements has been made and it is of important theoretical and practical significance to the development and reform of school physical education at this stage in our country.
复杂网络作为大量真实复杂系统的高度抽象,由于受计算机仿真和大规模的实际网络数据库的支持近年来在学术界倍受关注。规模越庞大,结构越复杂,网络的故障就越多,从而使网络面临的威胁和攻击也越来越多,因此网络的抗毁性逐渐成为学术界的一个新兴研究热点。几乎所有的复杂系统都可以抽象为复杂网络模型,这些网络大多数具有大量的节点,并且节点之间有着复杂的连接关系[1-2]。网络的抗毁性描述了网络在所处的自然环境下,遭受人为破坏时网络拓扑结构的可靠性,也就是说,抗毁性指的是破坏一个网络的拓扑结构的难易程度。抗毁性强的网络,其拓扑图应具有大的连通度。
关于网络的抗毁性测度,K.T.Newport[3-4]提出了经典的完全抗毁性测度——节点连通因子来表示网络的稳定性,Chvatalz[5]引入了图的坚韧度来测度网络的抗打击破坏能力; Barefoot[6]等人针对网络的完整度评价了网络的抗毁能力; 在2000年Albert等对无标度网络和随机网络分别进行了随机性攻击和选择性攻击,并对它们的抗毁性进行了比较。但是在以往对网络抗毁性能的评价中,大多数采用的是网络的最大簇尺寸作为评价标准,而忽略了其他较小的簇对网络抗毁性的影响。2005年,吴俊[7]等给出了新的连通性测度——通过加权的形式考虑了所有连通分支对网络抗毁性能的影响,并在此基础上针对随机性攻击(网络自身原因以及所处的自然环境等因素造成的节点的破坏)和选择性攻击分别定义了容错度和抗攻击度,但是在网络遭受攻击的过程中节点由于受自然环境和自身等因素的影响随时都有可能失效,从而造成对网络的破坏,所以要对网络的抗毁性进行定义就必须在考虑选择性攻击的同时把节点的随机失效也考虑进去,即同时考虑容错度和抗攻击度才能对网络的抗毁度进行更为确切的定义。在文献[8]中提到目前关于网络抗毁性主要有2种典型的定义——基于网络连通性的定义[9]和基于网络通信能力的定义。文中以当前网络与全连通网络的差异来表示网络的连通度,并通过加权的形式对全网连通度进行了定义,以此来保证所有的连通分支都对网络的抗毁能力起到影响。然后,考虑了随机性攻击(自然环境和网络自身等因素)在网络遭受选择性攻击时对网络抗毁性能的影响,即在随机失效率的前提下考虑网络遭受选择性攻击时网络的抗毁度,从而对网络的抗毁性测度做出较为确切的定义。
抗毁性是根据图论概念提出的,并从连通性的角度描述了网络拓扑结构的可靠性。在图论的学习中连通性指的是任意2个节点之间都存在一条路。而在实际中要求复杂网络全网保持连通是不太现实的同时也是毫无意义的。那么怎样才能有效地评价一个不连通网络的连通度是本节将要解决的一个主要问题。
结合文献[10]和[11] 中关于网络结构差异的思想,在下文中提出节点对的差异和连通分支的连通度这2个概念。
定义1 节点对的差异y等于2个节点间的最短路径(假设该对节点最短路径长为k)的数量x与全连通网络中这2个节点间长度等于k的路的数量y之比。
全连通网络中的任意2个节点均直接相连,所以有y=1,从而节点对的差异反映了当前网络与全连通网络的差异。y值越大,与全连通网络的差异就越小,则连通性就越好,反之就越差。而全连通网络的连通性是最好的,所以在文中用这种差异来定义连通分支的连通度。此外,当网络遭受破坏时,网络可能被打击成几个乃至许多个连通分支,那么怎样才能有效地定义遭受破坏后的网络的连通度,在下面的2个定义中,首先给出了连通分支的连通度,在此基础上,通过加权给出了全网的连通度。
定义2 连通分支的连通度
其中 Nk为第k个连通分支的节点数目; N为节点的总数目
定义3 全网连通度
其中 ω为连通分支的个数; Nk为第k个连通分支的节点数目; N为节点的总数目,lk为第k个连通分支的连通度。
从定义1可以看出,当两点直接相连时有y=1,由此分析定义2,当网络为全连通网络时,连通分支数ω=1且任何一对节点均直接相连,所以C有最大值1.C值越大,证明网络的连通性越好。
对于一个网络,抗毁性指的是至少需要破坏多少个节点或边才能使网络瘫痪。换句话说,网络的抗毁性研究的便是破坏一个网络连通性的难易程度。要破坏一个网络,除了人为蓄意攻击的因素外,还要受到网络自身和所处的自然环境等的限制,所以对网络进行人为蓄意攻击的同时还需要考虑网络自身和自然环境等因素对网络的破坏。除此,对于一个网络,不必对它的节点一一进行攻击,每个网络都有它的实用性,当被攻击到一定的程度时,虽然还保持一定的连通性,但是根据实际情况网络可能已经失去有用性,这时就不再对剩余的节点进行攻击。所以要在一定的网络有用性的前提下去考虑网络抗毁度,即要预先设定一个阈值,当网络的连通度被攻击到阈值时,就不再对网络进行攻击。
定义4 节点失效率:自然环境和网络自身等不可抗拒的因素对节点造成损坏的概率。也就是随机性攻击对节点造成损坏的概率。
定义5 网络抗毁度:对于一个初始连通度为 C且节点失效率为p的网络,当遭受的选择性攻击(人为攻击)使全网连通度达到阈值时节点的移除比例L.
注:①移除比例为被打击掉的节点和随机失效的节点在总节点中所占的比例; ②文中采用的选择性攻击策略是按照初始网络中节点的度从高到低依次进行打击(IB攻击策略[12])
当不同的网络的连通度被攻击到阈值时,节点的移除比例越大,证明该网络的抗毁性越强,或者可以看作当节点的移除比例相等时,全网连通度大的网络的抗毁能力较强。
结合以上定义和说明,下面给出测试方法的具体步骤。
1)对随机失效率p进行赋值并产生一个(0,1)之间的随机数。
2)若r<p,先对网络进行随机性攻击,然后对网络进行选择性攻击,如果全网连通度达到所给的阈值,则停止对网络进行攻击,并把这时网络节点的移除比例作为该网络的抗毁度。否则,转1.
3)若r>p,则对网络只进行选择性攻击,如果全网连通度达到所给的阈值,则停止对网络进行攻击,并把这时网络节点的移除比例作为该网路的抗毁度。否则,转1.
为了验证所提出的全网连通度的有效性,基于Matlab针对无标度网络和随机网络分别进行了仿真实验,结果发现无标度网络的容错度强于同规模的随机网络,但是,随机网络相对同规模的无标度网络有较强的抗攻击性,符合文献[13]中选择用最大簇尺寸和平均最短路径为指标时得出的结论,同时也符合文献[7]所得出的结论,从而对所提的全网连通度进行了有效的验证。由于2个网络的初始全网连通度不同,为了更方便和有效的比较二者在面临攻击时的抗毁能力,图1,图2的全网连通度均进行了归一化处理。
图1中虚线表示无标度网络在选择性攻击时的情况; 点划线表示随机网络在选择性攻击时的情况; 虚点线表示随机网络在随机性攻击时的情况; 实线表示无标度网络在随机攻击时的情况。从图中可以明显的看到无标度网络在面临选择性攻击时比随机网络崩溃的更早,显得异常的脆弱。只要少数节点被移除,无标度网络就会陷入瘫痪。另外从图中还看以观察到无标度网络在面临随机性攻击时具有非常高的容错度。此外,对实线和虚点线进行比较可以发现无标度网络在遭受随机性攻击时相对于随机网络有较高的容错度。
图1 N=100,平均度<k>=37.5的无标度网络和N=100,平均度<k>=37.5的随机网络分别在随机性攻击和选择性攻击下全网连通度随节点的移除的变化曲线
Fig.1 Connectivity variation curve with the removal of nodes of the BA network and ER network under the random and selective attack respectively, with N=100 and the average degree <k>=37.5
图2 N=100,平均度<k>=37.5的无标度网络和N=100,平均度<k>=37.5的随机网络分别在随机失效率的前提下遭受选择性攻击时全网连通度随节点移除的变化曲线
Fig.2 Connectivity variation curve with the removal of nodes of the BA network and ER network, with N=100 and the average degree <k>=37.5,undergoing the selective attack based on the random failure rate
图2中实线表示随机网络在随机失效率为0.2时遭受选择性攻击的情况; 点划线表示无标度网络在随机失效率为0.2时遭受选择性攻击的情况,虚点线表示随机网络在随机失效率为0.4时遭受选择性攻击的情况; 虚线表示无标度网络在随机失效率为0.4时遭受选择性攻击的情况。从图中可以看出,随着随机失效率的增大,无标度网络的抗毁性有明显的增强,这是因为随机失效率的增大意味着无标度网络遭受随机性攻击的可能性增大,而无标度网络在面临随机性攻击时有较强的抗毁性,故无标度网络随着随机失效率的增大表现出较强的抗毁性。随机网络随着随机失效率的增大部分图像呈现出下降的趋势,这是由于随机失效率的增大意味着随机网络遭受随机性攻击的可能性增大,而随机网络遭受随机性攻击时表现出了较弱的抗毁性,故部分图像呈现出下降的趋势。
取全网连通度的阈值为0.3,分别计算以上2种网络在随机失效率为0.2,0.4时的抗毁度,计算结果见表1.
从图2和表1中看以看到,复杂网络的抗毁度是随着随机失效率的变化而变化的,不同的随机失效率,网络表现出不同的抗毁度。所以在比较不同网络的抗毁能力的强弱时,把随机失效率考虑进去是必要的。
复杂网络的抗毁性是复杂网络理论的一个研究重点,它对复杂网络理论的研究具有重要的理论意义和实际价值。但是,由于对复杂网络的拓扑结构知之甚少,其抗毁性的评价到目前为止还没形成统一的方法。 文中在考虑随机失效率的前提下,从全网连通度的角度衡量了复杂网络的抗毁性能,结果发现网络的抗毁度是随着随机失效率的变化而变化的,也就是说网络的抗毁性是受自然环境和网络自身等不可抗拒因素影响的。所以说考虑了随机失效率的网络抗毁性的定义更加符合实际情况,从而为网络抗毁性的研究提供了一条新的思路。