无标度网络的鲁棒性及非线性整数规划设计

© 2014年。由爱思唯尔公司出版信息工程研究院负责评选和同行评议可在www.sciencedirect.com上在线获取ScienceDirectIERI Procedia 10（2014）177 - 1832014未来信息工程无标度网络Jianhua Zhang*，Bo Song，Zhaojun Zhang，Zhao Zhao江苏师范大学电气工程与自动化学院，徐州，中国摘要本文研究了无标度网络的连通性，引入了度方差来描述无标度网络的度与顶点平均度之间的数值距离，并将度方差作为无标度网络对失效鲁棒性的度量.根据度方差，研究了无标度网络对随机故障和蓄意攻击的鲁棒性，并讨论了节点对级联故障的防御能力。在平均度给定的情况下，根据度方差设计了一个非线性整数规划方案，对随机攻击和故意攻击进行防御。从该方案可以得到对级联故障的最优鲁棒性，该方案可以用于提高无标度网络的鲁棒性。版权所有© 2014由Elsevier B.V.发布 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究院负责评选和同行评议关键词：无标度网络;鲁棒性;度方差;非线性整数规划1. 介绍复杂网络在过去的几年中引起了越来越多的关注[1，2，3，4，5]，这一现象的最重要原因是由于它在现实中的广泛存在和应用，如互联网、经济系统、电网、生物系统、交通网络等等，它们都是现代社会不可或缺的。由于基础网络的安全性影响到多个方面，* 通讯作者。联系电话：+86 051683500273;传真：+86 051683500273。邮箱：zhangjianhua1980@126.com2212-6678 Crown版权所有© 2014由Elsevier B. V.出版 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究所负责的选择和同行评审178Jianhua Zhang等人/ IERI Procedia 10（2014）177在我们的现代生活中，许多研究人员都参与了这一领域的研究，并取得了许多有价值的成果[6，7，8，9]。自从小世界网络被发现以来，人们从多个方面对其行为进行了研究[2]，研究者也从现实出发构建了许多实际的复杂模型。现实中存在着许多无标度网络，其无标度性[3]一直受到国内外学者的关注[10，11，12]，许多网络具有无标度连通性分布[13，14]，这意味着无标度网络的度分布服从幂律分布[4，5，6]。根据度密度函数，人们发现了无标度网络的许多特征。从Motter等人 [15]中，我们知道复杂网络的节点i对级联故障具有负载能力，如下所示：Ci （1i= 1，2，n，N其中，L_0是容差参数，Li是节点i的初始负载，N是节点总数。虽然这一假设不能完全反映网络容量随时间变化的事实，但它可以告诉我们许多普遍规律，例如，如何设计方案来提高网络对随机攻击或故意攻击的鲁棒性。它也能给我们启发建立一个更好的模型来衡量网络的鲁棒性，并描述节点对攻击的抵抗能力。近年来，在信息科学与工程、统计与非线性物理、系统生物学、数学与社会科学等领域出现了许多新的概念和方案，用于研究解决问题的方法，特别是复杂网络问题[7，8，9]。复杂网络鲁棒性的最重要的一点是信息在网络拓扑顶点和其他物理量之间的流动，这种流动对网络的安全，如GPS安全、国防安全、军事安全、生态系统安全、供应链安全等都是至关重要的。复杂网络的安全性会从多方面影响人们的行为，因此必须设计一种更好的方案来度量网络的鲁棒性，保证系统中信息交换的畅通。Albertet al的作品。[3-4]证明了无标度网络具有鲁棒但脆弱的属性，这意味着它对随机故障是鲁棒的，但对故意攻击是脆弱的。因此，我们将设计一个模型，可以提高网络的抵抗随机故障或故意攻击。节点故障是复杂网络的严重威胁，它会改变网络中的流量平衡，导致网络中的负载重新分配，有时还会导致整个网络中的信息传输中断[15]。此外，微小的故障也会引起连锁故障，网络有时会崩溃本文的结构如下。在第二节中，我们讨论了无标度网络的连通性，它被看作是衡量无标度网络鲁棒性的一种度量。第三节介绍了度方差，第四节研究了无标度网络的最优鲁棒性。最后，在第五节中给出了结论。2. 无标度网络在本节中，我们研究无标度网络的连通性。关于复杂网络的鲁棒性度量有很多种，不同的度量在估计复杂网络的鲁棒性时具有不同的特点。在本文中，我们引入了无标度网络的另一种度量，称为连通性系数，如下所示，塞内加尔（1）/尼日利亚（1）其中n（l）是拓扑的边的总数。从连通性系数的定义可知，它可以作为无标度网络的一种度量，可以揭示网络的全局连通性。从复杂网络的性质和我们的方案可知，连通系数越大，鲁棒性越好，因此它是一个很好的衡量鲁棒性的指标。根据[16，17]，无标度网络的连接系数可以通过以下公式获得：Jianhua Zhang等人/ IERI Procedia 10（2014）1771792Sm（1）（1N）/2（2），中国（2，3）（二）其中m是无标度网络的最小度，N是顶点总数。32.521.510.5电话：+86-21 - 6666666传真：+86-21 - 66666666Fig. 1.连通系数m≠ 1的性质。我们根据图1所示的连通系数讨论了无标度网络的鲁棒性。从图1中，我们可以声明连接系数随着的增加而减少，因此我们知道鲁棒性随着的增加而减少。同时，从图1中我们知道，无标度网络的连通性更差。3. 度方差关于无标度网络鲁棒性的度量有很多，如两步度[16]和熵[17]，它们讨论了无标度网络在随机故障和故意攻击下的鲁棒性。不同的度量方法虽然效果不同，但从不同的角度考察系统的抗失效能力，讨论系统的异质性和鲁棒性，是目的一致的。从以往复杂网络的研究中，我们知道平均度是一种鲁棒性的度量，它可以反映复杂网络对随机故障和故意攻击的防御能力。同时，无标度网络的鲁棒性随着平均度的增加而增加，因此无标度网络更稳定。这是引入度方差[18]来研究无标度网络的异质性和鲁棒性复杂网络可以被表示为网络1、网络2、网络3和网络。网络1、网络2、网络、网络是网络4的一个子集，网络4是在顶点之间交换信息的边的集合。如果两个顶点之间有直接的关系，我们称这两个顶点之间有一条边连接，在这种情况下，我们定义信息流为1，否则信息流为0。度方差定义如下，V（k）<$E[k<$E（k）]2（三）其中，V（λ）表示方差，E（λ）表示数学期望，k是节点的度，度方差将用于衡量无标度网络的鲁棒性和异质性。根据方差的特性，我们知道V（）是描述度k到顶点平均度的平均距离的度量。因此，对于整个网络来说，该值越大，度的分布越差从[3-6]可知，最复杂的网络是无标度网络，S180Jianhua Zhang等人/ IERI Procedia 10（2014）177是幂律分布[16，17]，密度函数由下式给出：f（k）□， 中国（2，3）（四）要想知道密度函数的性质，首先要计算参数c。从[17]中，我们知道参数，c（） m1（五）其中m是顶点的最小度。由图2可知，参数c随着标度指数的增大而增大，随着m的增大而增大，同时增大的速度变快。从图2可以看出，参数c影响无标度网络的鲁棒性。181614121086420电话：+86-21 - 6666666传真：+86-21 - 66666666图二.参数c与的特性。根据（3）、（4）和（5），结合连续近似，我们可以得到无标度网络的度方差，M MM MV（k）E[kE（k）]2$E[k2]<$[E（k）]2k2f（k）<$[kf（k）]2<k2f（k）dk<$[kf（k）dk]2k m k mm（六）其中m是最小度，M是有限网络中存在的有效度截断。从文献[19]中的结果，我们知道，MmN1/（1）根据（6）和（7），度方差可以通过下式估计：（七）1312V（k）3m2（N1 1）（）2m2（11）22 我们可以从图3中宣布度方差V（k）随着标度指数的增加而减小，结合讨论[16，17，20]，我们知道随着异质性的增加，无标度网络的鲁棒性增加，因此我们可以宣布随着度方差的增加，鲁棒性也在这个意义上增加。但是我们知道度方差越大，度分布就越差。这两种观点的不同之处在于它们是对无标度网络级联故障的不同度量。度方差是描述度与平均度之间距离的度量，如果度方差变大，也就是说这个距离增大，度分布越不均匀，鲁棒性越差。在实际m=1m=2M=3CJianhua Zhang等人/ IERI Procedia 10（2014）177181网络中，我们知道度越均匀，信息交换越好，鲁棒性越好。6005004003002001000电话：+86-21 - 6666666传真：+86-21-666666662.8 2.9 3图三.度方差V对θ的性质。4. 稳健性优化设计通过以上分析，我们可以看出，对无标度网络鲁棒性的度量存在着许多差异，不同的度量方法会得到不同的结果。根据度方差可以设计无标度网络在随机失效和蓄意攻击下的鲁棒性的最优度量。在第三节中，我们发现度方差越小，鲁棒性越好，也就是说，网络越均匀，鲁棒性越好，因此我们构造了讨论无标度网络鲁棒性的最优方案。受[16-17]思想的启发，作者构造了非线性混合整数规划来讨论无标度网络的最优鲁棒性。本文提出的非线性混合整数规划如下，最小V（k）S.t.122m（1 <$N$N 1）常数;（八）1223，1mN 1，mZ哪里m（1N）是 平均 程度 的 无标度网络[17]。使用运算在实验室中对M2进行求解，可以根据不同的阶数得到阶数变化V的最佳值。非线性混合整数规划（8）的最小度m和标度指数由表1可知，随着给定整数k的增大，最小度的最优解迅速增大，标度指数的最优解有振荡，同时度方差的最优值有增大的趋势。由表1可知，无标度网络的最优鲁棒方案可以根据最优度方差的值来得到。表1方案（8）=2=3=4=5=6=7=8=9=10=11M1122334455v（k182Jianhua Zhang等人/ IERI Procedia 10（2014）1772.93092.40382.93092.58392.93092.67192.93092.72422.93092.7589V3.836532.90815.34653.25034.52883.039361.384120.9695.912166.732我们描绘了图中所示的最优设计（8）的特性4，它描述了最佳值，V/ 100，以及可选的解决方案， m和m具有不同的（？） 为了方便您查找由于V、、m和的关系，我们用V/ 100代替图4中的V从图4中，我们知道，随着k k的增加，最小度m增加，并且对于部分平均度k，例如，当k k 2，3时，m是常数并且V 增长，但标度指数  减少，当 年3月4日， M 和  增加，但V死亡， 而这现象仍在继续。这种跳跃现象是由约束条件和优化设计引起的。由图4可知，度方差的最优设计是讨论无标度网络最优鲁棒性的一个度量，我们也可以构造出防御无标度网络级联故障的最优方案。通过给出的最优方案，可以使无标度网络的度分布更加均匀，从而提高无标度网络的鲁棒性。这是基于节点度的最重要的度量。54.54mV/1003.532.521.510.502 3 4 5 6 7 8 9 10 11见图4。最佳值V/100，和m.5. 结论本文引入了无标度网络的连通系数和度方差。连通度系数描述了节点之间的相互关系，可以作为衡量复杂网络鲁棒性的一个指标。度方差是衡量网络在级联故障下鲁棒性的另一种度量，它描述了度与平均度之间的距离，反映了网络的异质性。我们知道度方差的数值越小，无标度网络的稳定性越好，鲁棒性越好。根据图3，我们可以宣布鲁棒性随着标度指数的增加而增加，并且根据度方差，我们可以设计相同的方案来防御现实中的随机故障和故意攻击。我们知道如果一个节点被攻击崩溃，可能会出现连锁故障，导致整个网络崩溃，因此无标度网络的最优鲁棒性非常重要，因此非线性混合整数规划是讨论最优鲁棒性的一种较好的方法。根据表1，我们可以得到方差度的最优值，以及不同平均度的最小度和标度指数的最优解。同时，根据这些特征，，m，V/100Jianhua Zhang等人/ IERI Procedia 10（2014）177183见图4。通过上述分析，该方案可以获得无标度网络的最优鲁棒性。确认本工作得到了国家自然科学基金（61304175、61104221和61305149）的资助。引用[1] 施特罗加茨自然，2001，410：268[2] Watt DJ，Strogaze SH. Nature，1998，393：440.[3] 阿尔伯特·巴拉巴西Science，1999，286：509.[4] Albert R，Barabasi AL. Rev. Mordern Phys.，2002，74：47。[5] 李文，李文，等.自然科学，2000，10（1）：100.[6] 曹志文，李玉霞，罗建华，陶丽，于红，赵军。物理、2007，16：3571。[7] 陈飞，陈志勤，袁志志.下巴物理、2007，16：287。[8] Dorogovtsev SN，Mendes JFF.高级物理学，2002，51：1079。[9] 纽曼MEJ。SIAM Rev.，2003，45：167。[10]孙海君，赵红，吴俊杰。Physica A，2008，387：6431.[11]赵L，光浩P，赖永春.物理评论E，2004，70：035101。[12]秦S，戴光正.下巴物理B，2009，18：383。[13]谢志，李新，王晓芳. Physica A，2007，384：725.[14]Liu MX，Ruan J. Chin.物理B，2009，18：2115。[15]Motter AE，Nishikawa T，Lai YC.，物理评论E，2002，66：065102。[16]吴志华，方宏杰.下巴物理快报，2008，25：3822。[17]王波，唐宏华，郭春春，修志良。Physica A，2006，363：591.[18]Tsukamoto E，Shirayama S. Physica A，2010，389：577.[19]科恩R，埃雷兹K，本-亚伯拉罕D，哈夫林S。物理修订信函：2000，85：4626。[20]Newnan MEJ，Strogatz SH，Watts DJ.Phys. Rev. 等，2001，64：026118。