相依网络在不同攻击策略下的鲁棒性

刘润然¹ 贾春晓¹ 章剑林¹ 汪秉宏²

1.杭州师范大学 阿里巴巴商学院与信息经济研究所 310036

2.中国科学技术大学 近代物理系 230026

摘要：相依网络的鲁棒性研究是当前网络科学研究的前沿热点之一。本文系统研究了相依网络在几种蓄意攻击策略下的级联失效过程，比较了几种攻击策略的特点，发现了同时考虑两个网络中相依节点度的特性比考虑单侧网络节点度的特性的攻击策略更有效。我们的工作不但有助于理解相依网络级联失效的过程，而且为找到相依网络的弱点进行有效的保护和攻击提供了有益的提示。

关键词: 相依网络，级联失效，蓄意攻击策略

ABSTRACT：The robustness of interdependent networks is one of the most important issues in network science and some important works has been devoted to the study of this problem. In this paper, we have studied the cascading failure processes of interdependent networks under several intentional attack strategies, and find that, compared with the strategies that only considered the connectivity of nodes in one single network, interdependent networks are more vulnerable when the connectivity of nodes in both networks are taken into account the attack strategy simultaneously. Our work maybe helpful for the understanding of cascading failures of interdependent networks, and could provide some helpful suggestions for the protection and attack of interdependent networks.

Keywords：Interdependent networks, cascading failure, intentional attack

项目基金：国家自然科学基金资助项目(91024026, 10975126)；浙江省自然科学基金（Y6110317）

1.相依网络的鲁棒性研究进展

       随着科学与技术的迅猛发展，各类基础设施之间的耦合和依赖变得越来越强，例如城市的供水系统，电力系统，燃气系统，交通系统以及通信系统之间都有着非常强的依赖关系[1,2]。具体的例子有：电力系统与通信系统之间的相互依赖关系，电力系统需要电信系统进行通信和调度，而通信系统又需要电力系统提供电力支持；类似的情况还有电力系统和铁路交通系统，铁路交通系统需要电力系统提供电力支持，而一些火电厂又需要铁路交通系统输送能源与物资。一个系统受到一点点的扰动可能会触发其它系统的失效进而又会影响到自身，从而会给整个社会带来灾难性的后果，例如：在2003年9月23日的意大利大停电事件，就是由一个电力站的失效导致很多电力节点与整个电网的脱离而失效，从而又导致很多互联网节点的失效，最终导致调度系统无法对整个电力网络进行有效的调控又诱发了更大规模的电力节点的失效[1]；另外一个国内的实例是在2008年春季中国南方的雪灾导致电力网络的失效，从而诱发了铁路交通网络的不畅，而铁路运输的不畅又导致了部分电厂无法得到能源的补给，从而使电力系统和铁路交通系统都难于恢复畅通，最终给华南的广大地区带来了非常严重的灾害。因此对这类相依系统的鲁棒性的研究有着非常强的现实意义[1-5]。

    复杂网络是研究复杂系统的有力工具之一，研究复杂网络的鲁棒性不但对于理解复杂系统的组织形式与功能之间的关系有着深刻的科学意义，而且为网络的攻击和保护提供了有效的理论依据[5-7]。目前有关复杂网络的鲁棒性的工作包括：基于渗流理论研究网络在删除部分节点后的连通性[8-11]；基于过载节点失效过程的网络上的动力学与网络结构的耦合[12-19]。然而这些工作主要是关于单一网络的，有关相依网络鲁棒性的研究还较少。2010年，Sergey V. Buldyrev等人在《Nature》杂志上首次发表了研究相依网络鲁棒性的著名论文，受到了极为广泛的关注[1]。该文提出了一个简单的相依网络级联失效的模型，不但刻画了相依网络级联失效的过程，而且发现相依网络从连通态（有序）到破碎态（无序）是一个非连续相变过程，这与通常的复杂网络的座逾渗模型的连续相变有着很大的不同；随后的研究还发现降低相依网络之间的耦合还可以使相变现象从一级相变变成二级相变，这很类似与水在发生气液相变时的临界现象[3]；Xuqing Huang等人也研究了相依网络在单侧节点受到蓄意攻击下的鲁棒性[4]；董高高也研究了双侧节点受到蓄意攻击下的鲁棒性[20]。然而当前有关同时考虑相依节点对的权重的攻击策略的研究还相对较少。本文研究了相依网络在几种攻击策略的鲁棒性，找出了最有效的攻击策略，从而发现了相依网络中最为脆弱的节点。

2相依网络的蓄意攻击策略以及鲁棒性

2. 1相依网络的级联失效过程

       相依网络可以形象描述相互依赖的系统，由两个网络A和B组成，每个网络内部的节点由连接边（connectivity links）连在一起，表示网络内部节点的连接关系，而跨网络的节点由相依边（dependency links）连在一起，表示网络之间节点的相依关系[1,21]。当相依网络中A或B网络的节点受到攻击而失效的时候，网络A或B会破碎成几个碎片，该模型假定只有属于网络A或网络B极大簇（giant component）的节点能够保持功能，而属于其它碎片的节点会失去功能。假定网络A中部分节点受到初始攻击而失效，网络A会破碎为若干碎片，不属于A网络极大簇的节点也会失效； A网络中的失效的节点也会导致B网络中相应的节点失效，从而导致导致网络B的破碎，不属于网络B极大簇的节点也因此失效；再进一步，B网络中的失效的节点也会导致A网络中相应的节点失效，从而导致导致网络A再次发生破碎。如此反复进行下去，经历一定步数的迭代后[Number of Iterations(NOI)]，系统会达到稳定；当系统达到稳定时，只有属于互联极大簇（网络A的极大簇中的节点和网络B中极大簇的节点完全是由相依边连在一起的）的节点才能保持功能。整个级联失效的过程，如下图所示：

图1，相依网络级联失效的迭代的过程，在a阶段，A网络的一个节点因受到攻击而失效；在b阶段，与该失效节点相连的边被删去，同时与之相依的B网络中的节点也因此失效，与之相连的边也被删除，不属于A网络极大簇的节点a₁₁，a₁₂失效；在c阶段，b₂₁，b₂₂因与失效节点a₁₁，a₁₂相依而失效，不属于B网络的极大簇的节点b₂₃失效；在d阶段，B网络中失效的节点b₂₃又导致了A网络的a₃₃节点失效，整个系统达到稳态。该图引自参考文献[1]。

       相依网络中互联极大簇是衡量相依网络在受到攻击后维持自身功能的重要指标，类似于渗流理论中的序参量极大簇，在本文中我们把互联极大簇标记为S。在本文中接下来的部分，我们将重点研究互联极大簇在不同攻击策略下随攻击强度下的变化规律。

2.2 相依网络的蓄意攻击策略

    相依网络在随机攻击策略下的鲁棒性已经有较为深入的理论研究，然而在相依网络中，一个节点的失效会导致与之相依节点的失效，因此一个节点对于维持整个网络的连通性的能力不仅与自身有关而且与它相依的节点有关。在本文中我们对相依网络中相依节点对进行加权，这里的权重我们假定就是这对节点对于维持相依网络功能的重要性，然后依据它们的权重的大小进行攻击。

攻击策略I：对A网络中节点度进行降序排列，攻击排序靠前的比例为1-p的节点，因此剩下比例为p的节点保留了下来。该策略仅仅考虑了单侧节点的度。

攻击策略II：对AB网络中相依边两端的相依节点对进行加权，第n对节点的权重是： ，其中， 表示A网络中第n个节点的度， 表示B网络中第n个节点的度，然后依据权重对这些节点对进行排序，攻击排序靠前的比例为1-p的节点，保留比例为p的部分节点。该策略同时考虑了相依节点度的特性。

攻击策略III：类似于攻击策略II，不过加权方式改变为： ，同样， 表示A网络中第n个节点的度， 表示B网络中第n个节点的度，同样依据权重对这些节点对进行排序，攻击排序靠前的比例为1-p的节点，保留比例为p的部分节点。该策略也同时考虑了相依节点度的特性。

       在这里，通过参数p我们可以调节对相依网络的攻击强度。在接下来的部分我们将展示网络的互联极大簇S随参数p的变化规律。这里我们的研究的相依网络是由两个随机网络组成，两个网络中的节点之间的相依关系是随机建立的，也就是说网络与网络之间相依节点度的相关性等于0。

2.3 相依网络在不同攻击策略下的鲁棒性

图2，(a)在随机攻击下，不同网络规模的互联极大簇随参数p的变化；(b)，NOI随p的变化，插图表示再双对数坐标下，NOI在相变点处与网络规模N的关系。在此图中，相依网络中两个网络的平均度都为<k>=4，每条曲线都来自1000次平均的结果。

       相依网络在随机攻击下，互联极大簇随攻击强度1-p的变化呈现一级（非连续）相变的行为，这与经典随机网络的座逾渗的二级（连续）相变有着很大的不同，如图2(a)所示，我们可以发现在不同的系统规模下，所有的曲线可以相交于一点，当系统的规模N趋向于无穷大的时候，我们可以认为互联极大簇S可以从此点跳到0，此点可以近似于一级相变的相变点；另外图2(b)展示了相依网络达到稳态时所经历的迭代步数[Number of Iterations(NOI)]，我们发现NOI在相变点附近有一个峰值，当系统规模达到无穷大时，NOI所对应的p值就是一级相变的相变点。从图2b的插图中我们可以发现，NOI与网络的规模N呈现幂函数的关系，也就是当N趋近于无穷大时，NOI也趋向于无穷大。对于相依的两个随机网络，网络破碎的临界值的理论结果等于 [1,22]，因此对于平均度为4的相依网络，其发生的破碎的临界点 ，我们的模拟可以验证这一结果。

图3，在攻击策略I下，相依网络的鲁棒性： (a)不同网络规模的互联极大簇随参数p的变化；(b)NOI随p的变化，插图表示再双对数坐标下，NOI在相变点处与网络规模N的关系。在此图中，相依网络中两个网络的平均度都为<k>=4，每条曲线都来自1000次平均的结果。

       在图3中，我们研究了相依网络在攻击策略I下的鲁棒性，发现了与随机攻击类似的一级相变的现象，但是临界点 ，明显超过随机攻击的临界点 ，这说明相依网络在蓄意攻击策略下变得更加脆弱了。

图4，在攻击策略II下，相依网络的鲁棒性： (a)不同网络规模的互联极大簇随参数p的变化；(b)NOI随p的变化，插图表示再双对数坐标下，NOI在相变点处与网络规模N的关系。在此图中，相依网络中两个网络的平均度都为<k>=4，每条曲线都来自1000次平均的结果。

       在图4中，我们研究了相依网络在攻击策略II下的鲁棒性，同样发现了一级相变的现象，但是临界点 ，明显超过随机攻击与攻击策略I的临界点 和 ，这说明相依网络在此种攻击策略下变得进一步脆弱了。这个结果也证明了考虑相依节点对度之和的攻击策略比考虑单侧节点度的大小的攻击策略更有效。

图5，在攻击策略III下，相依网络的鲁棒性： (a)不同网络规模的互联极大簇随参数p的变化；(b)NOI随p的变化，插图表示再双对数坐标下，NOI在相变点处与网络规模N的关系。在此图中，相依网络中两个网络的平均度都为<k>=4，每条曲线都来自1000次平均的结果。

       在图5中，我们研究了相依网络在攻击策略III下的鲁棒性，同样发现了一级相变的现象，相变点 ，与攻击策略II的 类似。这个结果进一步证明了考虑相依节点对度的特性的攻击策略比考虑单侧节点度的大小的攻击策略更有效。

3结论与展望

       本文中，我们比较了相依网络在几种攻击策略下的鲁棒性，发现了考虑相依节点对度的特性的攻击策略比考虑单侧节点度的特性的攻击策略更有效。我们的工作对于理解相依网络级联失效的过程有着重要的作用，并为找到相依网络的弱点进行有效的保护和攻击提供了有益的提示。在本文的研究中，我们仅仅研究了相依随机网络的鲁棒性，其它复杂网络例如：无标度网络小世界网络的鲁棒性还有待进一步研究[5-7]；此外，我们研究的是相依节点度不相关的网络，今后的研究我们还将研究相依网络度相关网络的鲁棒性[24], 对于正相关的网络，度大的节点往往与度大的节点相依，在随机攻击下这样的网络会更加稳健[25]，在蓄意攻击下，这样的网络显然会更加脆弱；对于负相关的网络，相依节点对的度之和会变得更加均匀，这样会导致网络在蓄意攻击下会更加脆弱还是更加稳健？这是一个值得研究的问题。还有需要注意的是，我们这里仅仅依据节点的度进行加权，是否有其它加权方法可以使我们找到更加有效的攻击手段？例如：节点的介数，这又是一个非常值得研究的问题。

4参考文献

[1] S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, and S. Havlin, Nature (London) 464, 1025 (2010);

[2]S. Havlin, N. A. M. Araujo, S. V. Buldyrev, C. S. Dias, R. Parshani, G. Paul, and H. E. Stanley, arXiv:1012.0206;

[3] R. Parshani, S. V. Buldyrev, S. Havlin, Phys. Rev. Lett. 105, 048701 (2010).

[4] X. Huang, J. Gao, S. V. Buldyrev, S. Havlin, and H.E. Stanley, Phys. Rev. E 83, 065101(R) (2011);

[5]汪小帆,李翔,陈关荣,复杂网络理论及其应用[M],北京:清华大学出版社(2006);

[6] S. N. Dorogovtsev, A.V. Goltsev, and J. F. F.Mendes, Rev.Mod. Phys. 80, 1275 (2008).

[7]何大韧,刘宗华,汪秉宏,复杂系统与复杂网络[M],北京:高等教育出版社,(2009);

[8] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 85, 4626 (2000);

[9] D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett. 85, 5468 (2000);

[10] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 86, 3682 (2001);

[11]D. Stauffer and A. Aharony, Introduction to Percolation Theory (Taylor & Francis, London, 1992);

[12] A. E.Motter and Y.-C. Lai, Phys. Rev. E 66, 065102(R) (2002);

[13]L. Zhao, K. Park, and Y.-C. Lai, Phys. Rev. E 70, 035101(R)(2004);

[14]L. Zhao, K. Park, Y.-C. Lai, and N. Ye, Phys. Rev. E 72, 025104(R) (2005).

[15] A. E. Motter, Phys. Rev. Lett. 93, 098701 (2004); E. J. Lee, K.

[16] W.-X. Wang, and G. Chen, Phys. Rev. E 77, 026101 (2008);

[17]R. Yang, W.-X. Wang, Y.-C. Lai, and G. Chen, Phys. Rev. E 79, 026112 (2009);

[18]W.-X.Wang and Y.-C. Lai, Phys. Rev. E 80, 036109 (2009);

[19]D. J. Watts, Proc. Natl. Acad. Sci. U.S.A. 99, 5766 (2002);

[20] G.-G. Dong, J.-X. Gao, L.-X. Tian, R.-J. Du, Y.-H. He, arXiv:1108.5788;

[21] R. Parshani, S. V. Buldyrev, and S. Havlin, Proc. Natl. Acad. Sci. USA 108, 1007 (2011);

[22] S.-W. Son, P. Grassberger, and M. Paczuski, Phys. Rev. Lett. 107, 195702 (2011);

[23] J. Gao, S. V. Buldyrev, Shlomo Havlin, H. Eugene Stanley,Phys. Rev. Lett. 107, 195701 (2011);

[24] 史定华，网络度分布理论，北京：高等教育出版社(2011);

[25] S. V. Buldyrev, N. W. Shere, and G. A. Cwilich, Phys. Rev. E 83, 016112 (2011).

     你

相关插图请见原文PDF文件：

刘润然 相依网络在不同攻击策略下的鲁棒性.pdf