Emergence of scaling in random networks

a r X i v :c o n d -m a t /0008064v 1 [c o n d -m a t .d i s -n n ] 3 A u g 2000Error and attack tolerance of complex networksR´e ka Albert,Hawoong Jeong,Albert-L´a szl´o Barab´a siDepartment of Physics,University of Notre Dame,Notre Dame,IN 46556Many complex systems display a surprising degree of tolerance against er-rors.For example,relatively simple organisms grow,persist and reproduce de-spite drastic pharmaceutical or environmental interventions,an error tolerance attributed to the robustness of the underlying metabolic network [1].Complex communication networks [2]display a surprising degree of robustness:while key components regularly malfunction,local failures rarely lead to the loss of the global information-carrying ability of the network.The stability of these and other complex systems is often attributed to the redundant wiring of the func-tional web defined by the systems’components.In this paper we demonstrate that error tolerance is not shared by all redundant systems,but it is displayed only by a class of inhomogeneously wired networks,called scale-free networks.We find that scale-free networks,describing a number of systems,such as the World Wide Web (www)[3–5],Internet [6],social networks [7]or a cell [8],display an unexpected degree of robustness,the ability of their nodes to com-municate being unaffected by even unrealistically high failure rates.However,error tolerance comes at a high price:these networks are extremely vulnerable to attacks,i.e.to the selection and removal of a few nodes that play the mostimportant role in assuring the network’s connectivity.Such error tolerance and attack vulnerability are generic properties of communication networks,such as the Internet or the www,with complex implications on assuring information readiness.The increasing availability of topological data on large networks,aided by the computer-ization of data acquisition,has lead to major advances in our understanding of the generic aspects of network structure and development[9–16].The existing empirical and theoretical results indicate that complex networks can be divided into two major classes based on their connectivity distribution P(k),giving the probability that a node in the network is connected to k other nodes.Thefirst class of networks is characterized by a P(k)that is peaked at an average k and decays exponentially for large k.The most investigated examples of such exponential networks are the random graph model of Erd˝o s and R´e nyi[9,10]and the small-world model of Watts and Strogatz[11],both leading to a fairly homogeneous network,in which each node has approximately the same number of links,k≃ k .In contrast,results on the world-wide web(www)[3–5],Internet[6]and other large networks[17–19]indicate that many systems belong to a class of inhomogeneous networks,referred to as scale-free networks,for which P(k)decays as a power-law,i.e.P(k)∼k−γ,free of a characteristic scale.While the probability that a node has a very large number of connections(k>> k ) is practically prohibited in exponential networks,highly connected nodes are statistically significant in scale-free networks(see Fig.1).We start by investigating the robustness of the two basic network models,the Erd˝o s-R´e nyi(ER)model[9,10]that produces a network with an exponential tail,and the scale-free model[17]with a power-law tail.In the ER model wefirst define the N nodes,and then connect each pair of nodes with probability p.This algorithm generates a homogeneous net-work(Fig.1),whose connectivity follows a Poisson distribution peaked at k and decaying exponentially for k>> k .The inhomogeneous connectivity distribution of many real networks is reproduced by the scale-free model[17,18]that incorporates two ingredients common to real networks: growth and preferential attachment.The model starts with m0nodes.At every timestep t a new node is introduced,which is connected to m of the the already existing nodes.The probabilityΠi that the new node is connected to node i depends on the connectivity k i ofthat node,such thatΠi=k i/jk j.For large t the connectivity distribution is a power-lawfollowing P(k)=2m2/k3.The interconnectedness of a network is described by its diameter d,defined as the av-erage length of the shortest paths between any two nodes in the network.The diameter characterizes the ability of two nodes to communicate with each other:the smaller d is,the shorter is the expected path between works with a very large number of nodes can have a rather small diameter;for example the diameter of the www,with over800million nodes[20],is around19[3],while social networks with over six billion individuals are be-lieved to have a diameter of around six[21].To properly compare the two network models we generated networks that have the same number of nodes and links such that P(k)follows a Poisson distribution for the exponential,and a power-law for the scale-free network.Error tolerance—To address the networks’error tolerance,we study the changes in the diameter when a small fraction f of the nodes is removed.The malfunctioning(absence)of a node in general increases the distance between the remaining nodes,since it can eliminate some paths that contribute to the system’s interconnectedness.Indeed,for the exponential network the diameter increases monotonically with f(Fig.2a),thus,despite its redundant wiring(Fig.1),it is increasingly difficult for the remaining nodes to communicate with each other.This behavior is rooted in the homogeneity of the network:since all nodes have approximately the same number of links,they all contribute equally to the network’s diameter,thus the removal of each node causes the same amount of damage.In contrast,we observe a drastically different and surprising behavior for the scale-free network(Fig.2a): the diameter remains unchanged under an increasing level of errors.Thus even when as high as5%of the nodes fail,the communication between the remaining nodes in the network is unaffected.This robustness of scale-free networks is rooted in their extremely inhomogeneous connectivity distribution:since the power-law distribution implies that the majority of nodes have only a few links,nodes with small connectivity will be selected with much higher probability,and the removal of these”small”nodes does not alter the path structure of the remaining nodes,thus has no impact on the overall network topology.Attack survivability—An informed agent that attempts to deliberately damage a net-work,such as designing a drug to kill a bacterium,will not eliminate the nodes randomly,but will rather target the most connected nodes.To simulate an attack wefirst remove the most connected node,and continue selecting and removing nodes in the decreasing order of their connectivity k.Measuring the diameter of an exponential network under attack,wefind that,due to the homogeneity of the network,there is no substantial difference whether the nodes are selected randomly or in decreasing order of connectivity(Fig.2a).On the other hand,a drastically different behavior is observed for scale-free networks:when the most connected nodes are eliminated,the diameter of the scale-free network increases rapidly, doubling its original value if5%of the nodes are removed.This vulnerability to attacks is rooted in the inhomogeneity of the connectivity distribution:the connectivity is ensured by a few highly connected nodes(Fig.1b),whose removal drastically alters the network’s topology,and decreases the ability of the remaining nodes to communicate with each other.Network fragmentation—When nodes are removed from a network,clusters of nodes, whose links to the system disappear,can get cut offfrom the main cluster.To better understand the impact of failures and attacks on the network structure,we next investigate this fragmentation process.We measure the size of the largest cluster,S,shown as a fraction of the total system size,when a fraction f of the nodes are removed either randomly or in an attack mode.Wefind that for the exponential network,as we increase f,S displays a threshold-like behavior such that for f>f c≃0.28we have S≃0.A similar behavior is observed when we monitor the average size s of the isolated clusters(i.e.all the clusters except the largest one),finding that s increases rapidly until s ≃2at f c,after which it decreases to s =1.These results indicate the following breakdown scenario(Fig.4):For small f,only single nodes break apart, s ≃1,but as f increases,the size of the fragments that fall offthe main cluster increases,displaying a singular behavior at f c.At f c the system practically falls apart,the main cluster breaking into small pieces,leading to S≃0,and the size of the fragments, s ,peaks.As we continue to remove nodes(f>f c),we fragment these isolated clusters,leading to a decreasing s .Since the ER model is equivalent to theinfinite dimensional percolation[22],the observed threshold behavior is qualitatively similar to the percolation critical point.However,the response of a scale-free network to attacks and failures is rather different (Fig.3b).For random failures no threshold for fragmentation is observed,rather the size of the largest cluster slowly decreases.The fact that s ≃1for most f indicates that the network is deflated by nodes breaking offone by one,the increasing error level leading to the isolation of single nodes only,not clusters of nodes.Thus,in contrast with the catastrophic fragmentation of the exponential network at f c,the scale-free network stays together as a large cluster for very high values of f,providing additional evidence of the topological stability of these networks under random failures.This behavior is consistent with the existence of an extremely delayed critical point(Fig.3),the network falling apart only after the main cluster has been completely deflated.On the other hand,the response to attack of the scale-free network is similar(but swifter)to the response to attack and failure of the exponential network(Fig.3b):at a critical threshold f sf c≃0.18,smaller than the value f e c≃0.28observed for the exponential network,the system breaks apart,forming many isolated clusters(Fig.4).While great efforts are being made to design error tolerant and low yield components for communication systems,little is known about the effect of the errors and attacks on the large-scale connectivity of the network.To demonstrate the impact of our model based studies to these systems,next we investigate the error and attack tolerance of two networks of increasing economic and strategic importance:the Internet and the www.Recently Faloutsos et al.[6]investigated the topological properties of the Internet at the router and inter-domain level,finding that the connectivity distribution follows a power-law, P(k)∼k−2.48.Consequently,we expect that it should display the error tolerance and attack vulnerability predicted by our study.To test this,we used the latest survey of the Internet topology,giving the network at the inter-domain(autonomous system)level.Indeed,wefind that the diameter of the Internet is unaffected by the random removal of as high as2.5%of the nodes(an order of magnitude larger than the failure rate(0.33%)of the Internet routers[23]),while if the same percentage of the most connected nodes are eliminated(attack),d more than triples(Fig.2b).Similarly,the large connected cluster persists for high rates of random node removal,but if nodes are removed in the attack mode,the size of the fragments that break offincreases rapidly,the critical point appearing at f I c≃0.03(Fig.3b).The www forms a huge directed graph whose nodes are documents and edges are the URL hyperlinks that point from one document to another,its topology determining the search engines’ability to locate information on it.The www is also a scale-free network:the probabilities P out(k)and P in(k)that a document has k outgoing and incoming links follow a power-law over several orders of magnitude,i.e.P(k)∼k−γ,withγin=2.1andγout=2.45 [3,4,24].Since no complete topological map of the www is available,we limited our study to a subset of the web containing325,729nodes and1,469,680links( k =4.59)[3].Despite the directedness of the links,the response of the system is similar to the undirected networks we investigated earlier:after a slight initial increase,d remains constant in the case of random failures,while it increases for attacks(see Fig.2c).The network survives as a large cluster under high rates of failure,but the behavior of s indicates that under attack the system abruptly falls apart at f w c=0.067(Fig.3c).In summary,wefind that scale-free networks display a surprisingly high degree of toler-ance against random failures,a property not shared by their exponential counterparts.This robustness is probably the basis of the error tolerance of many complex systems,ranging from cells[8]to distributed communication systems.It also explains why,despite frequent router problems[23],we rarely experience global network outages or,despite the temporary unavailability of many webpages,our ability to surf and locate information on the web is unaffected.However,the error tolerance comes at the expense of attack survivability:the diameter of these networks increases rapidly and they break into many isolated fragments when the most connected nodes are targeted.Such decreased attack survivability is useful for drug design[8],but it is less encouraging for communication systems,such as the Internet or the www.While the general wisdom is that attacks on networks with distributed resource management are less successful,our results indicate that the topological weaknesses of thecurrent communication networks,rooted in their inhomogeneous connectivity distribution, have serious effects on their attack survivability,that could be exploited by those seeking to damage these systems.REFERENCES[1]Hartwell,L.H.,Hopfield,J.J.,Leibler,S.&Murray,A.W.,From molecular to modularcell biology,Nature402,C47-C52(1999).[2]Claffy,K.,Monk,T.E.&McRobb,D.Internet tomography,Nature web matters,7January1999,</webmatters/tomog/tomog.html>.[3]Albert,R.,Jeong,H.&Barab´a si,A.-L.Diameter of the World-Wide Web,Nature401,130-131(1999).[4]Kumar,R.,Raghavan,P.,Rajalopagan,S.&Tomkins,A.Extracting large-scale knowl-edge bases from the web,Proc.25th VLDB Conf.,Edinburgh,1999.[5]Huberman,B.A.&Adamic,L.A.Growth dynamics of the World-Wide Web,Nature401,131(1999).[6]Faloutsos,M.,Faloutsos,P.&Faloutsos,C.On Power-Law Relationships of the InternetTopology,ACM SIGCOMM’99,mun.Rev.29,251-263(1999).[7]Wasserman,S.&Faust,K.Social Network Analysis(Cambridge University Press,Cam-bridge,1994).[8]Jeong,H.,Tombor,B.,Albert,R.,Oltvai,Z.&Barab´a si,A.-L.The large-scale organi-zation of metabolic networks.(preprint).[9]Erd˝o s,P.&R´e nyi,A.On the evolution of random graphs.Publ.Math.Inst.Hung.Acad.Sci.5,17-60(1960).[10]Bollob´a s,B.Random Graphs(Academic Press,London,1985).[11]Watts,D.J.&Strogatz,S.H.Collective dynamics of’small-world’networks.Nature393,440-442(1998).[12]Zegura,E.W.,Calvert,K.L.&Donahoo,M.J.A Quantitative Comparison of Graph-based Models for Internet Topology.IEEE/ACM Transactions on Networking5,770-787 (1997).[13]Cohen,J.E.,Briand,F.&Newman,munity food webs:data and theory(Springer-Verlag,Berlin1990).[14]Maritan,A.,Colaiori,F.,Flammini,A.,Cieplak,M.,&Banavar,J.Universality Classesof Optimal Channel Networks.Science272,984-986(1996).[15]Banavar,J.R.,Maritan,A.&Rinaldo,A.Size and form in efficient transportationnetworks.Nature399,130-132(1999).[16]Barth´e l´e my,M.&Amaral,L.A.N.Small-World Networks:Evidence for a CrossoverPicture.Phys.Rev.Lett.82,3180-3183(1999).[17]Barab´a si,A.-L.&Albert,R.Emergence of Scaling in Random Networks.Science286,509-511(1999).[18]Barab´a si,A.-L.,Albert,R.&Jeong,H.Mean-field theory for scale-free random net-works.Physica272A,173-187(1999).[19]Redner,S.,How popular is your paper?An empirical study of the citation distribution.Euro.Phys.J.B4,131-134(1998).[20]Lawrence,S.&Giles,C.L.Accessibility of information on the web.Nature400,107-109(1999).[21]gram,The Small-World Problem.Psychol.Today2,60-67(1967).[22]Bunde,A.&Havlin S.(editors)Fractals and Disordered Systems(Springer,New York,1996).[23]Paxson,V.End-to-End Routing Behavior in the Internet.IEEE/ACM Transactions onNetworking5,601-618(1997).[24]Adamic,L.A.The Small World Web.Lect.Notes Comput.Sci1696,443-452(1999).FIGURESFIG.1.Visual illustration of the difference between an exponential and a scale-free network. The exponential network a is rather homogeneous,i.e.most nodes have approximately the same number of links.In contrast,the scale-free network b is extremely inhomogeneous:while the ma-jority of the nodes have one or two links,a few nodes have a large number of links,guaranteeing that the system is fully connected.We colored with red thefive nodes with the highest number of links, and with green theirfirst neighbors.While in the exponential network only27%of the nodes are reached by thefive most connected nodes,in the scale-free network more than60%are,demonstrat-ing the key role the connected nodes play in the scale-free network.Note that both networks contain 130nodes and215links( k =3.3).The network visualization was done using the Pajek program for large network analysis<http://vlado.fmf.uni-lj.si/pub/networks/pajek/pajekman.htm>.0.000.010.021015200.000.010.020510150.000.020.044681012abcfdInternetwwwAttackFailureAttackFailureSFE AttackFailure FIG.2.Changes in the diameter of the network as a function of the fraction of the removed nodes.a ,Comparison between the exponential (E)and scale-free (SF)network models,each containing N =10,000nodes and 20,000links (i.e. k =4).The blue symbols correspond to the diameter of the exponential (triangles)and the scale-free (squares)network when a fraction f of the nodes are removed randomly (error tolerance).Red symbols show the response of the exponential (diamonds)and the scale-free (circles)networks to attacks,when the most connected nodes are removed.We determined the f dependence of the diameter for different system sizes (N =1,000,5,000,20,000)and found that the obtained curves,apart from a logarithmic size correction,overlap with those shown in a ,indicating that the results are independent of the size of the system.Note that the diameter of the unperturbed (f =0)scale-free network is smaller than that of the exponential network,indicating that scale-free networks use more efficiently the links available to them,generating a more interconnected web.b ,The changes in the diameter of the Internet under random failures (squares)or attacks (circles).We used the topological map of the Internet,containing 6,209nodes and 12,200links ( k =3.4),collected by the National Laboratory for Applied Network Research </Routing/rawdata/>.c ,Error (squares)and attack (circles)survivability of the world-wide web,measured on a sample containing 325,729nodes and 1,498,353links [3],such that k =4.59.012301<s > a n d S0.00.20.40120.00.20.401210-110101102f<work fragmentation under random failures and attacks.The relative size of the largest cluster S (open symbols)and the average size of the isolated clusters s (filled symbols)in function of the fraction of removed nodes f for the same systems as in Fig.2.The size S is defined as the fraction of nodes contained in the largest cluster (i.e.S =1for f =0).a ,Fragmentation of the exponential network under random failures (squares)and attacks (circles).b ,Fragmentation of the scale-free network under random failures (blue squares)and attacks (red circles).The inset shows the error tolerance curves for the whole range of f ,indicating that the main cluster falls apart only after it has been completely deflated.Note that the behavior of the scale-free network under errors is consistent with an extremely delayed percolation transition:at unrealistically high error rates (f max ≃0.75)we do observe a very small peak in s ( s max ≃1.06)even in the case of random failures,indicating the existence of a critical point.For a and b we repeated the analysis for systems of sizes N =1,000,5,000,and 20,000,finding that the obtained S and s curves overlap with the one shown here,indicating that the overall clustering scenario and the value of the critical point is independent of the size of the system.Fragmentation of the Internet (c )and www (d ),using the topological data described in Fig.2.The symbols are the same as in b .Note that s in d in the case of attack is shown on a different scale,drawn in the right side of the frame.While for small f we have s ≃1.5,at f w c=0.067the average fragment size abruptly increases,peaking at s max ≃60,then decays rapidly.For the attack curve in d we ordered the nodes in function of the number of outgoing links,k out .Note that while the three studied networks,the scale-free model,the Internet and the www have different γ, k and clustering coefficient [11],their response to attacks and errors is identical.Indeed,we find that the difference between these quantities changes only f c and the magnitude of d ,S and s ,but not the nature of the response of these networks to perturbations.f≈0.05f≈0.18f≈0.45 FIG.4.Summary of the response of a network to failures or attacks.The insets show the cluster size distribution for various values of f when a scale-free network of parameters given in Fig.3b is subject to random failures(a-c)or attacks(d-f).Upper panel:Exponential networks under random failures and attacks and scale-free networks under attacks behave similarly:for small f clusters of different sizes break down,while there is still a large cluster.This is supported by the cluster size distribution:while we see a few fragments of sizes between1and16,there is a large cluster of size9,000(the size of the original system being10,000).At a critical f c(see Fig.3)the network breaks into small fragments between sizes1and100(b)and the large cluster disappears. At even higher f(c)the clusters are further fragmented into single nodes or clusters of size two. Lower panel:Scale-free networks follow a different scenario under random failures:The size of the largest cluster decreases slowly asfirst single nodes,then small clusters break off.Indeed,at f=0.05only single and double nodes break off(d).At f=0.18,when under attack the network is fragmented(b),under failures the large cluster of size8,000coexists with isolated clusters of size1through5(e).Even for unrealistically high error rate of f=0.45the large cluster persists, the size of the broken-offfragments not exceeding11(f).。

复杂⽹络中聚类算法总结⽹络，数学上称为图，最早研究始于1736年欧拉的哥尼斯堡七桥问题，但是之后关于图的研究发展缓慢，直到1936年，才有了第⼀本关于图论研究的著作。

20世纪60年代，两位匈⽛利数学家Erdos和Renyi建⽴了随机图理论，被公认为是在数学上开创了复杂⽹络理论的系统性研究。

之后的40年⾥，⼈们⼀直讲随机图理论作为复杂⽹络研究的基本理论。

然⽽，绝⼤多数的实际⽹络并不是完全随机的。

1998年，Watts及其导师Strogatz在Nature上的⽂章《Collective Dynamics of Small-world Networks》揭⽰了复杂⽹络的⼩世界性质。

随后，1999年，Barabasi及其博⼠⽣Albert在Science上的⽂章《Emergence of Scaling in Random Networks》⼜揭⽰了复杂⽹络的⽆标度性质(度分布为幂律分布)，从此开启了复杂⽹络研究的新纪元。

随着研究的深⼊，越来越多关于复杂⽹络的性质被发掘出来，其中很重要的⼀项研究是2002年Girvan和Newman在PNAS上的⼀篇⽂章《Community structure in social and biological networks》，指出复杂⽹络中普遍存在着聚类特性，每⼀个类称之为⼀个社团(community)，并提出了⼀个发现这些社团的算法。

从此，热门对复杂⽹络中的社团发现问题进⾏了⼤量研究，产⽣了⼤量的算法，本⽂试图简单整理⼀下复杂⽹络中聚类算法，希望对希望快速了解这⼀部分的⼈有所帮助。

本⽂中所谓的社团跟通常我们将的聚类算法中类(cluster)的概念是⼀致的。

0. 预备知识为了本⽂的完整性，我们⾸先给出⼀些基本概念。

⼀个图通常表⽰为G=(V,E)，其中V表⽰点集合，E表⽰边集合，通常我们⽤n表⽰图的节点数，m表⽰边数。

⼀个图中，与⼀个点的相关联的边的数量称为该点的度。

复杂网络外部同步最新研究进展作者：陈正伟马继伟石咏来源：《电子世界》2013年第16期【摘要】简单介绍了当前复杂网络外部同步的最新发展，通过回顾复杂网络的研究历程，结合当前的研究热点，具体分析了不连续复杂网络外部同步、两个耦合复杂动力学网络的有限时间外部同步、复杂网络有限时间随机广义外部同步。

得出了将来研究复杂网络的一个趋势，以期待为今后复杂网络的研究提供有益借鉴。

【关键词】复杂网络；有限时间同步；外部同步；随机网络1.引言20世纪60年代，由匈牙利数学家Erdǒs和Rényi建立的随机图理论，在数学上开创了复杂网络理论的系统性研究。

80年代以来，以互联网为代表的计算机和信息工程技术的迅猛发展使人类社会大步迈入了一个“网络时代”[1]。

从互联网到万维网、从电力网到交通网、从大脑神经网到新陈代谢网、从科研合作网到各种社会关系网等，足见复杂网络广泛存在于我们生活中[2-4]。

同步现象是复杂网络典型动力学行为之一，近年来复杂网络同步问题受到了广泛的关注，其中，文献[5]用主稳定函数方法研究了网络同步状态的稳定性；文献[6-7]研究了小世界网络与无尺度网络的同步问题；文献[8]研究了时变动态网络的同步问题；文献[9]认为在特定的耦合方式下，耦合矩阵的第二大特征值可以表征网络的同步能力；文献[10]认为在通常情况下，只要耦合强度的值足够大，都会使耦合系统进入同步状态，这些工作都极大地丰富了有关复杂网络同步的研究内容。

然而上述研究的主要内容是复杂网络的“内部同步”，即一个网络内部节点间的同步。

两个或多个网络间的同步行为，即“外部同步”却研究较少。

本文将着重介绍最新的复杂网络外部同步研究成果，通过分析不同的研究思路，得到未来复杂网络的研究热点。

2.复杂网络外部同步最新研究具体分析2.1 不连续复杂网络的广义同步近年来复杂网络外部同步引起了人们的广泛关注，文献[11]首先研究了两个单向耦合网络之间的外部同步，并导出了有相同拓扑结构的两个网络之间的同步准则。

一文读懂社会网络分析(SNA)理论、指标与应用开新坑！社交网络分析（又称复杂网络、社会网络，Social Network Analysis）是诞生于数学图论、计算机科学、物理学的交叉碰撞中的一门有趣的学科。

缘起：我研究SNA已经有近2年的时光，一路坎坷走来有很多收获、踩过一些坑，也在线上给很多学生讲过SNA的入门知识，最近感觉有必要将心得和基础框架分享出来，抛砖引玉，让各位对SNA感兴趣的同学们一起学习进步。

我的能力有限，如果有不足之处大家一起交流，由于我的专业的影响，本文的SNA知识可能会带有情报学色彩。

面向人群：优先人文社科类的无代码学习，Python、R的SNA 包好用是好用，但是对我们这这些社科的同学来说门槛太高，枯燥的代码首先就会让我们丧失学习兴趣。

特征：类综述文章，主要目的是以通俗的语言和精炼的框架带领各位快速对SNA领域建立起一个全面的认知，每个个关键概念会附上链接供感兴趣的同学深入学习。

开胃菜：SNA经典著作分享《网络科学引论》纽曼 (访问密码 : v9d9g3)2概述:什么是网络？我们从哪些角度研究它？1) 认识网络SNA中所说的网络是由节点（node，图论中称顶点vertex）和边（edge）构成，如下图。

每个节点代表一个实体，可以是人、动物、关键词、神经元；连接各节点的边代表一个关系，如朋友关系、敌对关系、合作关系、互斥关系等。

最小的网络是由两个节点与一条边构成的二元组。

Les Miserables人际关系网络2) 构建网络就是建模马克思说过，“人的本质在其现实性上，它是一切社会关系的总和。

” 事实上，当我们想快速了解一个领域，无论该领域是由人、知识、神经元乃至其他实体集合构成，利用SNA的方法将实体及其相互关系进行抽象和网络构建，我们就完成了对某一领域的“建模”，这个模型就是网络图，拿科学网络计量学家陈超美的观点来说，借助网络图，“一图胜千言，一览无余”。

3) 社会网络类型这里展示了常见和常用的网络类型名词。

基于复杂网络的电网元件脆弱性分析关学忠;刘金龙;高哲;于镝【摘要】The power grid was described a complex network composed of nodes and lines and its vulnerability was analyzed through discussing both nodes and lines' fragility;and employing electrical degree-betweenness index and triple electrical index to assess the vulnerability of nodes and lines in the power grid was proposed. In the IEEE-118 bus system, the cascading failure simulation and global efficiency were implemented to meas-ure the power grid' s vulnerability index.The fault simulation results show that protecting the nodes with higher triple electrical index and the lines with higher electrical degree-betweenness index can ensure safe and steady operation of the power grid.%把电网看成是由节点和线路组成的复杂网络,分别通过节点和线路的脆弱性来分析电网的脆弱性. 提出用电气度介数指标和电气三重数指标来评价线路的脆弱性和节点的脆弱性. 在IEEE-118总线系统中采用联锁故障模拟,用全局效能来衡量电网的脆弱性. 仿真结果表明:保护电气三重数指标高的节点和电气度介数指标高的线路可以有效保障电网的安全稳定工作.【期刊名称】《化工自动化及仪表》【年(卷),期】2015(042)010【总页数】5页(P1104-1108)【关键词】电网;脆弱性分析;复杂网络;电气度介数指标;电气三重数指标;全局效能;移除策略【作者】关学忠;刘金龙;高哲;于镝【作者单位】东北石油大学电气信息工程学院,黑龙江大庆 163318;海洋石油工程股份有限公司,天津300461;辽宁大学轻型产业学院,沈阳110036;东北石油大学电气信息工程学院,黑龙江大庆 163318【正文语种】中文【中图分类】TH862+.79随着社会的发展和人们生活水平的不断提高，电力成为人类不可或缺的资源。

a rX iv:112.206v1[physi cs .data-an]1D ec21Catastrophic Cascade of Failures in Interdependent Net-works S.Havlin Minerva Center and Department of Physics,Bar-Ilan University,52900Ramat-Gan,Israel N.A.M.Ara ´u jo Computational Physics for Engineering Materials,IfB,ETH Z¨u rich,Schafmattstr.6,8093Z¨u rich,Switzerland S.V.Buldyrev Department of Physics,Yeshiva University,500West 185th Street,New York 10033USA Center for Polymer Studies and Department of Physics,Boston University,Boston Massachusetts 02215,USA C.S.Dias GCEP-Centro de F´ısica da Universidade do Minho,4710-057Braga,Portugal R.Parshani Minerva Center and Department of Physics,Bar-Ilan University,52900Ramat-Gan,Israel G.PaulCenter for Polymer Studies and Department of Physics,Boston University,Boston Massachusetts 02215,USAH.E.StanleyCenter for Polymer Studies and Department of Physics,Boston University,Boston Massachusetts 02215,USAc Societ`a Italiana di Fisica 12H.E.Stanley Summary.—Modern network-like systems are usually coupled in such a waythat failures in one network can affect the entire system.In infrastructures,biology,sociology,and economy,systems are interconnected and events taking place in onesystem can propagate to any other coupled system.Recent studies on such coupledsystems show that the coupling increases their vulnerability to random failure.Prop-erties for interdependent networks differ significantly from those of single-networksystems.In this article,these results are reviewed and the main properties discussed.1.–IntroductionThe last decade witnessed an intensive study of complex networks[1,2,3,4,5, 6]boosted by several real-world data revealing complex structures in the topology of their network like,Internet,airport connections,and power grids[7].Recently,special emphasis has been focused on the robustness of such systems to random failures or malicious attacks[8,9,10,11,12,13,14].Most of these works have been focused on single,isolated networks where no interaction with other networks is considered,i.e., the behavior of the system is independent of any other,coupled with it.Such conditions rarely occur in nature nor in technology.Typically,systems are interconnected and events taking place in one are likely to affect the others.Only recently[15,16],the effect of coupled networks has been considered,where a failure of one node in a network may lead to a cascade of failures in the entire system.In this manuscript we review these results, obtained through analytical and numerical approaches,based on percolation principles, which are rather surprising.In Fig.1is a scheme,from Peerenboom et al.[17],showing the interdependence of the relevant infrastructures for daily life,namely,oil,transportation,electric power, natural gas,water,and telecommunications.Not only all infrastructures depend on the electrical-power network,as one would expect,but also electrical power depends on the others,i.e.,a bidirectional coupling exists between all networks.This strong coupling can lead to catastrophic effects when,for some reason,a failure occurs in one of the networks.In September28th,2003,Italy was affected by a country-wide blackout[18], which was understood due to the coupling between the electrical power and communi-cation networks.In Fig.2is the map of Italy with the electrical power network on top. Each node is a power station and the edges represent the connection between stations. Slightly shifted to the top,is a scheme of the communication network that controls the power distribution,where the nodes are servers and the edges are links between them.In both cases,nodes are positioned based on their real geographical coordinates and com-munication servers are connected to their geographically nearest power station.When, for some reason,a failure occurs in one power station(red node in Fig.2.a),the node is removed from the network,and consequently four servers are turned offdue to the lack ofCatastrophic Cascade of F ailures in Interdependent Networks3Fig.1.–Interdependency of infrastructures(After Peerenboom et al.[17]).power supply.When these servers go down,three other servers(in green)become inac-tive since they are disconnected from the giant communication cluster.Then,a sequence of events takes place,in a cascade fashion,where the power stations connected to these servers are shut down(see Fig.2.b)and a set of other power stations(in green)become disconnected from the power grid giant component and,therefore,become inactive(see Fig.2.c).This example shows how a fail in a single power station can lead to a cascade of events ending in a blackout spanning over more than half of the system.Not only in infrastructures onefinds interdependent networks.From economy to biology there exist many examples of coupled systems.The network of banks is inter-dependent to the network of insurance companies,as well as to the network offirms in differentfields.These interconnections played a major role in the recentfinancial crisis. The human body networks are also interdependent,e.g.,the cardio-vascular,the respi-ratory,and the nervous systems depend on each other in order to function.Examples of interdependent networks can also be found in social sciences.Therefore,the study of the properties of coupled networks is a matter of paramount importance in multidisci-plinary science.In this article,we review the recent analytical and numerical results on their percolation properties.We start by recalling the main features of single networks, in Sec.2.In Secs.3and4the case of fully and partially interdependent networks are discussed.We presentfinal remarks in Sec.5.2.–Single Network RobustnessFor more than a decade the critical properties of isolated(single)networks have been studied extensively,see e.g.,[5,6].One relevant question is related with percolation,4H.E.StanleyFig.2.–Cartoon of a typical cascade obtained by implementing the described model on the real coupled system in Italy.Over the map is the network of the Italian power network and,slightly shifted to the top,is the communication network.Every server was considered to be connected to the geographically nearest power station.(After Buldyrev et al.[15])i.e.,the emergence of a giant cluster when nodes(or links)are sequentially added to the network[19,20,21,22,23].Due to symmetry reasons,for a single network,the problem can also be formulated in the inverse way.Let us consider an initial configuration of a network made of nodes and links connecting them.How the fraction of nodes in the giant cluster(largest one)is changed when a fraction1−p of nodes(or links)is removed?The fraction of the giant component is called the order parameter in the language of critical phenomena[19,20].Several models of networks have been proposed.Their description and critical prop-erties can be found elsewhere[5,6].In this article we focus on two types of model networks:a random graph(Erd˝o s-R´e nyi)[21,22,23]and a scale-free network(Barab´a si-Albert)[24].The Erd˝o s-R´e nyi(ER)network is a random graph obtained by randomly distributing M links between N nodes,being a statistical ensemble with equal probabil-ity for any generated configuration.The scheme in Fig.3.a is one possible configuration. On the other hand,the Barab´a si-Albert(BA)is a network which was grown under the preferential attachment rule,i.e.,at each iteration a new node is added to the network and connected to m already existing nodes with a probability of linking to a certain node proportional to the actual degree(number of links)of that node.A typical configuration obtained with this model is shown in Fig.3.b.These two models of generating networks lead to different topologies and statistical properties.For the ER network,since links are distributed in an uncorrelated way,theCatastrophic Cascade of F ailures in Interdependent Networks5Fig.3.–Single networks.a)Classical Erd˝o s-R´e nyi model and b)Barab´a si-Albert model. degree distribution is Poissonian,i.e.,the frequency of nodes with k links is[21],λkP(k)=exp(−λ)6H.E.Stanley The power-law nature of the degree distribution in a scale-free graph leads to richer percolation properties in this type of networks.In fact,such properties are dependent on the value of the degree exponentγ.For2≤γ≤3,the giant component only vanish for p c=0and no percolation transition occurs[26].However,for values ofγabove3,alike ER a second-order transition is found but with different critical exponents[5,25].Yet, the network is very robust to random failure which explains,for example,the stability of the Internet to random failures and the high longevity of viruses in the Internet,despite the large number of anti-virus softwares in the market.For both types of networks,when the percolation transition occurs,it is of second-order nature,meaning that a smooth decrease of the order parameter with the increasing fraction of removed nodes is observed.Besides,this fraction,at the critical point,is rather large(p c is low)being a sign of robustness in the system.As discussed below, this is not the case,when interdependent systems are considered.Recently,several studies have been published,discussing how to change the stochastic rule of percolation to obtain an abrupt transition[27,28,29,30,31,32]in a single network.When coupled interdependent systems are considered the order of the transition becomes naturally of first order nature[15,16].3.–Interdependent Networks RobustnessDespite the technological and fundamental relevance of coupled networks,only re-cently they have been considered and their percolation properties have been studied [15,16].The results of Buldyrev et al.[15]disclose an emergency of novel percolation properties under coupling not predicted from the behavior of single networks.To account for the coupling,let us consider two different networks,hereafter referred as A and B.Every A-node depends on a B-node,and vice versa,i.e.,a bidirectional,one-to-one coupling exists such that if node A i depends on node B i then node B i depends on node A i.The dependency is such that coupled nodes are only active if both are connected to the giant component of their work A and network B have degree distributions P A(k)and P B(k)respectively.The dependency links between the networks are achieved by randomly connecting(A i,B i)pairs of nodes in both networks under the constraint of having only one inter-network link per node.Percolation properties are studied by randomly removing nodes in the network A, mimicking a failure or malicious attack.When a node A i is removed,its A-links and the coupled node B i are also removed.As discussed above,in the context of the2003 blackout in Italy,removing the node A i can ignite failures in other nodes.All A-nodes which become disconnected from the giant cluster through A i become inactive and are removed together with their correspondent B-nodes.Analogously,all B-nodes bridged to the giant component through node B i are also removed.The same procedure is, recurrently,followed for all removed nodes and their counterparts in the other network leading to cascading failures between the two networks.This procedure reveals,as in the case of single networks,discussed in Sec.2,that when a fraction of nodes1−p is removed,a percolation transition occurs at a certain threshold,p=p c.Only for valuesCatastrophic Cascade of F ailures in Interdependent Networks7Fig.4.–Fraction of nodes in the giant component(p n/p)after n stages of cascading failures for different realizations of two coupled ER networks with the same degree distribution and128000 nodes.Initial removal is just below the percolation threshold with p=2.4554/<k>=p c. (After Buldyrev et al.[15]).of p above this threshold a giant mutually connected cluster exists.Below it,the entire system becomes completely fragmented.For two coupled ER networks the problem can be solved explicitly using generating functions[15,33,34,35].When the two networks have the same degree,i.e.,<k>A=< k>B=<k>,the value of p c is,1p c=8H.E.StanleyFig.5.–Scaled distribution of the number of stages in the cascade failures for two Erd˝o s-R´e nyi graphs,with the same degree distribution,at criticality,for different values of N.(After Buldyrev et al.[15]).At p c,the average number number of stages in the cascade scales with N1/4(see Fig.5).In Fig.6we plot the threshold,p c,and the fraction of nodes in the mutual giant component,µ∞,for different ratios between the average degrees of the networks,<k>A /<k>B.When the average degree is the same for both networks,<k>A=<k>B,as discussed above,the threshold is given by eq.(4)andµ∞at p c is nonzero,i.e.,the coupled system is more vulnerable than the single network case and the percolation transition is first order.As the ratio between the average degree of the networks decreases,both the threshold and the jump at the transition diminish.Therefore,the smaller the ratio the more resilient is the system to failures.In the limit where the ratio approach zero,the single-network features are recovered,i.e.,the transition becomes of second-order nature, with p c=1/<k>.When coupled scale-free networks are considered,a percolation transition,at nonzero p c,is obtained even for values of the degree exponent2<γ≤3.This is in contrast to the single network case,where a giant cluster is observed for any positive fraction p of nodes(see Sec.2).Analogously to ER networks,the coupling between scale-free networks significantly increases the vulnerability of the system,with a larger p c compared to the case of a single network.Since hubs can have a low-degree counterpart node,their vulnerability evinces with the coupling.In contrast to single networks,the broader the degree distribution the larger is p c,i.e.,the smaller the fraction of nodes that needs to be removed to fully fragment the system.In general,the coupling between networks,increase the vulnerability of the system due to the cascade of failures that can be activated by removing a small fraction of nodes.Catastrophic Cascade of F ailures in Interdependent Networks 9Fig.6.–For two coupled Erd˝o s-R´e nyi networks,the threshold p c and the fraction of nodes in the mutual giant cluster at the transition,µ∞,are plotted as a function of the ratio between the average degrees of networks A and B,<k >A /<k >B .Findings are summarized in Fig.7.While for a single network,a second-order percolation transition is observed where the order parameter vanishes smoothly at criticality,for coupled systems,the transition occurs for larger p c (lower fraction of removed nodes),and is rather abrupt,characterized by a discontinuity in the order parameter.In the next section,the case of partially dependent networks is reviewed.SingleCascades,SuddenbreakdownCoupled 1st order1012nd order p c p p c P ∞Fig.7.–The order parameter (fraction of sites in the giant component)as a function of the fraction of left nodes in single and coupled networks.For single networks,above the percolation threshold a smooth increase of the order parameter is observed,with a critical exponent β.However,for strongly coupled networks,an abrupt transition is observed,characteristic of first-order transitions,due to the cascade phenomenon discussed in the text.10H.E.Stanleyp P 8Fig.8.–Order parameter P ∞as a function of the fraction of nodes left p for Erd˝o s-R´e nyi and scale-free network (γ=2.7)with strong and weak coupling.Both systems contain 5×104nodes.For both network types,first-order transitions occurs for strong coupling in contrast to second order transition in weak coupling.(After Parshani et al.[16]).4.–Partially Dependent NetworksFrequently,in real-world systems not all the nodes in one network are interdependent on the other network and vice versa,via bidirectional links.Instead,some nodes may be autonomous and independent on nodes from the other networks.For example,in the communication/power-grid system,a fraction of servers may be protected by emergency power supplies which are activated when the local power station is shut down.Parshani et al.[16]have studied the behavior of partially interdependent networks under random failure and found quantitatively how reducing the coupling improves the robustness of the system against random attack and how percolation transition changes from first to second order.The model introduced in Sec.3,can now be generalized to account for partially coupling between networks.Two coupled networks are then considered,A and B ,with degree distributions P A (k )and P B (k ),respectively.In network A ,a fraction of nodes q A depends on nodes from network B .Likewise,in network B ,a fraction of nodes q B depends on nodes in A .In the limit of q A =q B =1the fully interdependent system,discussed above,is recovered.Following the procedure described before,1−p nodes are randomly removed and the percolation properties of the system studied.If a removed node has a dependent in the other network,this node is also removed.All nodes linked to the correspondent giant component solely through the removed nodes are also considered inactive.In Fig.8we show the curves of the fraction of sites belonging to the mutually connected giant component,P ∞,as a function of p .ER and scale-free networks (with γ=2.7)have beenCatastrophic Cascade of F ailures in Interdependent Networks11010203040n 00.10.20.30.40.5P n (a)051015n00.050.10.150.20.25P n (b)Fig.9.–The giant component as a function of the number of cascade failures in two coupled Erd˝o s-R´e nyi networks,with N A =N B =8×105and <k >A =<k >B =2.5,for two different coupling strengths.(a)p =0.7455,q A =0.7,and q B =0.6(first order).(b)p =0.605,q A =0.2,and q B =0.75(second order).Solid lines correspond to results obtained from theory based on generating functions.(After Parshani et al.[16]).considered,with strong (q A =q B =q =0.8)and weak (q =0.1)coupling.For both systems in the strong coupling case,the robustness of the coupled networks systems is similar to that observed in the limit of q =1(see Sec.3).Reducing the coupling leads to a second order phase transition similar to single networks (the case of q =0).Increasing the coupling leads to a percolation transition at larger p c and to a change from second order,under weak coupling,to first order for strong coupling.The giant component as a function of the number of iterations in the cascade of failures,close to the transition point,for a strong and weak coupled system is shown in Fig.9.Two coupled ER networks have been considered,with N A =N B =8×105and the same average degree of nodes,with strong and weak coupling.In the strong coupling regime,a plateau is obtained followed by an abrupt decrease of the order parameter,similar to the case q =1of the a first-order transition.While,in the weak coupling regime,the order parameter smoothly vanish with the number of iterations of the cascades.Results for partially dependent networks are summarized in the two-parameter phase diagram of Fig.10.In the horizontal axis is the fraction of removed nodes in network A ,1−p ,while in the vertical one is the fraction of independent nodes in the same network,1−q A .The value of q B is chosen to be q B =1.Two different regimes can be identified in the diagram.In the right side of the diagram (below the curve),no finite giant component exists in network B at p c .That is,the system is below p c .In the left side,a giant component exists in the system.This two different regimes are separated by a phase transition line.When one crosses this line,a percolation transition is observed.The solid line corresponds to a first-order transition,characterized by a jump in the order parameter at the transition point.The dashed line stands for a second-order transition,where a continuous change of the order parameter is obtained.For a fully coupled system,12H.E.StanleyFig.10.–Diagram for percolation in two coupled networks in the two-parameter space,namely, the fraction of independent nodes in one network and the fraction of removed nodes in the same network.For weak coupling(large fraction of independent nodes)the transition is continuous (dashed line).Below a certain fraction of independent nodes,due to the coupling strength,the transition becomes discontinuous(first order).The vulnerability of the system increases with increasing in the coupling strength.(After Parshani et al.[16]).1−q A=0,only a small fraction of nodes needs to be removed to observe a fragmentation of the whole system in a discontinuous way.As one increases the fraction of independent nodes in the system,the fraction of removed nodes at the transition increases,meaning that the vulnerability of the system increases.Thisfirst-order line of the transition ends at a critical point above which the transition is no longer abrupt,being smooth and of second-order nature.5.–Final remarksIn this review,the recent work by Buldyrev et al.[15]and Parshani et al.[16]on the percolation properties of interdependent networks have been revisited.The review is based on a Lecture given by S.Havlin in the June2010Varenna School.Modern systems tend to be more coupled together.Infrastructures,biology,sociology and economy sys-tems are interconnected such that events taking place in one system may propagate and influence other coupled networks.Recent studies[15,16]show that coupling between systems increases their vulnerability to random failure.Properties of interdependent net-works significantly differ from the ones of a single network.In this article,these results are reviewed and the main properties are discussed.When a system of two interdepen-Catastrophic Cascade of F ailures in Interdependent Networks13 dent networks is considered,where nodes in one network have a bidirectional coupling with nodes in the other,the percolation properties are significantly affected.Due to cou-pling,not only the transition threshold is increased but also the order of the transition changes.The presence of interdependency between nodes in different networks,such that if one of the nodes is inactive the other can not function as well,leads to catastrophic effects when some nodes are removed from the system.A cascade of events is then ignited leading to an abrupt decomposition of the mutually connected giant component. For two interconnected ER graphs,when nodes are removed randomly,a percolation transition is observed.While for a single network the transition is always second order, for the coupled system the transition is ratherfirst order and the threshold corresponds to much less removed nodes.This increase in vulnerability with the coupling is also observed for scale-free networks and,unlike single networks,even for values of the degree exponent below three a percolation transition is observed.Tuning the fraction of interdependent nodes shifts the percolation threshold.The stronger the coupling the lower the fraction of nodes that needs to be removed to fully fragment the giant component.Yet,the order of the transition changes from second order,in the weak coupling regime,tofirst order under strong coupling.In the two-parameter diagram,of coupling and fraction of removed nodes,there are two transition lines,one offirst order and the other a second order line that mutually touch in a critical point.These interesting results raise new questions in thefield of complex networks.As a natural follow up,it is interesting to understand what happens when different types of networks are coupled,with special focus on real networks.The effect of different types of inter-networks connections is also relevant.Besides,understanding how rewiring of the system may improve the resilience to failures is of paramount interest.14H.E.Stanley REFERENCES[1]R.Albert and A.-L.Barab´a si.Statistical mechanics of complex networks.Rev.Mod.Phys.,74:47,2002.[2]S.N.Dorogovtsev and J.F.F.Mendes.Evolution of networks.Adv.in Phys.,51:1079,2002.[3]M.E.J.Newman.The structure and function of complex networks.SIAM Rev.,45:167,2003.[4]works:An Introduction.Oxford University Press,Oxford,2010.[5]S.N.Dorogovtsev,A.V.Goltsev,and J.F.F.Mendes.Critical phenomena in complexnetworks.Rev.Mod.Phys.,80:1275,2008.[6]R.Cohen and plex networks:structure,robustness and function.CambridgeUniversity Press,Cambridge,2010.[7] A.Clauset,C.R.Shalizi,and M.E.J.Newman.Power-law distributions in empirical data.SIAM Rev.,51:661,2009.[8]R.Albert,Jeong H.,and A.-L.Barab´a si.Error and attack tolerance of complex networks.Nature,406:378,2000.[9]R.Cohen,K.Erez,D.ben-Avraham,and S.Havlin.Breakdown of the internet underintentional attack.Phys.Rev.Lett.,86:3682,2001.[10]R.Albert,I.Albert,and G.L.Nakarado.Structural vulnerability of the North Americanpower grid.Phys.Rev.E,69:025103,2004.[11] A.A.Moreira,J.S.Andrade Jr,H.J.Herrmann,and J.O.Indekeu.How to make a fragilnetwork robust and vice versa.Phys.Rev.Lett.,102:018701,2009.[12]P.Holme,B.J.Kim,C.N.Yoon,and S.K.Han.Attack vulnerability of complex networks.Phys.Rev.E,65:056109,2002.[13] C.M.Schneider, A.A.Moreira,J.S.Andrade Jr.,S.Havlin,and H.J.Herrmann.Mitigation of malicious attacks on networks.Preprint,2010.[14]H.J.Herrmann,C.M.Schneider,A.A.Moreira,J.S.Andrade Jr.,and S.Havlin.Onion-like network topology enhances robustness against malicious attacks.accepted for JSTAT, 2010.[15]S.V.Buldyrev,R.Parshani,G.Paul,H.E.Stanley,and S.Havlin.Catastrophic cascadeof failures in interdependent networks.Nature,464:1025,2010.[16]R.Parshani,S.V.Buldyrev,and S.Havlin.Interdependent networks:reducing thecoupling strength leads to a change from afirst to second order percolation transition.Phys.Rev.Lett.,105:048701,2010.[17]J.Peerenboom,R.Fischer,and R.Whitfield.Recovering from disruptions ofinterdependent critical infrastructures.Pro.CRIS/DRM/IIIT/NSF Workshop Mitigat.Vulnerab.Crit.Infrastruct.Catastr.Failures,2001.[18]V.Rosato,L.Issacharoff, F.Tiriticco,S.Meloni,S.De Porcellinis,and R.Setola.Modelling interdependent infrastructures using interacting dynamical models.Int.J.Crit.Infrastruct.,4:63,2008.[19] D.Stauffer and A.Aharony.Introduction to Percolation Theory.Taylor&Francis,London,1994.[20] A.Bunde and S.Havlin,editors.Fractals and Disordered Systems.Springer,Heidelberg,1996.[21]P.Erd˝o s and A.R´e nyi.On random graphs.I.Publ.Math.(Debrecen),6:290,1959.[22]P.Erd˝o s and A.R´e nyi.On the evolution of random graphs.Publ.Math.Inst.Hung.Acad.Sci.,5:17,1960.[23] B.Bollob´a s.Random Graphs.Academic Press,London,1985.Catastrophic Cascade of F ailures in Interdependent Networks15 [24] A.-L.Barab´a si and R.Albert.Emergence of scaling in random networks.Science,286:509,1999.[25]R.Cohen,D.ben-Avraham,and S.Havlin.Percolation critical exponents in scale-freenetworks.Phys.Rev.E,66:036113,2002.[26]R.Cohen,K.Erez,D.ben-Avraham,and S.Havlin.Resilience of the internet to randombreakdowns.Phys.Rev.Lett.,85:4626,2000.[27] D.Achlioptas,R.M.D’Souza,and J.Spencer.Explosive percolation in random networks.Science,323:1453,2009.[28]R.M.Ziff.Explosive growth in biased dynamic percolation on two-dimensional regularlattice networks.Phys.Rev.Lett.,103:045701,2009.[29] F.Radicchi and S.Fortunato.Explosive percolation in scale-free networks.Phys.Rev.Lett.,103:168701,2009.[30] F.Radicchi and S.Fortunato.Explosive percolation:A numerical analysis.Phys.Rev.E,81:036110,2010.[31]N.A.M.Ara´u jo and H.J.Herrmann.Explosive percolation via control of the largestcluster.Phys.Rev.Lett.,105:035701,2010.[32]R.A.da Costa,S.N.Dorogovtsev, A.V.Goltsev,and J.F.F.Mendes.”Explosivepercolation”transition is actually continuous.arXiv:1009.2534v2,2010.[33]M.E.J.Newman.Spread of epidemic disease on networks.Phys.Rev.E,66:016128,2002.[34]J.Shao,S.V.Buldyrev,R.Cohen,M.Kitsak,S.Havlin,and H.E.Stanley.Fractalboundaries of complex networks.Europhys.Lett.,84:48004,2008.[35]J.Shao,S.V.Buldyrev,L.A.Braunstein,S.Havlin,and H.E.Stanley.Structure of shellsin complex networks.Phys.Rev.E,80:036105,2009.。