Breakdown of an Inhomogeneous Scale-free Network under Intentional Attack
物理学院物理系99级 林国基
Abstract
Using a recently introduced network model with node and connectiondiversity, we study the breakdown of different scale-free networks underintentional attacks. Our simulation results show that inhomogeneous networksare more sensitive to intentional attack than the homogeneous ones, and thatthe centralization of the networks is an important variable, reflecting thecharacteristics of the network under intentional attack. Using a recentlyintroduced method we can theoretically develop the critical point of theinhomogeneous networks.
Complex networks, whose nodes represent individuals or organizations andlinks mimic the interactions among them can be properly used to describemany real-life systems such as the Internet [1], World Wide Web [2], electronic power grid [3], citation pattern ofscientific publications [4] and metabolic and proteininteraction networks [5,6]. Different network models havebeen discussed, characterized and documented. They have developed from theearly homogeneous models, such as the random graph model of Erdos and Renyi [7], the small world model of Watts and Strogatz [3], and thescale-free models of Barabasi and Albert [8](we call the BA model or the BAnetworks in this letter). The later properly describes the important scalingbehavior observed in many networks in reality [1-6]. The scaling behavior meansthat a node has k connections follows a scale-free distribution , with an exponent ranges between 2 and 3. Thepresence of nodes with a very large number of connections is the keycharacteristic of these networks. Previous study has showed that [9], in the BA network, if the nodes of the network are randomlyremoved, the network can maintain its integrity even when a high proportionof nodes are removed. However, if the nodes with the highest connectivityare targeted, the network will crash into fragments with deletions of only asmall number of nodes.
In this letter we focus on the stability of inhomogeneous networks with node and connection diversity [10](we call it the inhomogeneous model or the inhomogeneous networks) under intentional attack. In Ref. [10], a modelof inhomogeneous network with node and connection diversity is put forwardto describe the real-life complex networks more accurately. The network's ranges from 2 to and the centralization index is muchcloser to the network in reality than the BA model. We show that theseinhomogeneous networks are more sensitive to the attack than the classicalBA network. We find that the centralization is an important variable thatreflects the properties of networks under intentional attack.
The model of inhomogeneous network consists of two types of node denoted byA and B. Type A node can be linked and link to other nodes, while type Bnode can only link to others but not allowed to be linked. That means linksbetween two type B nodes are prohibited. The connectivity of nodeiis defined as the total number of links pointing to it. The following rulesare used to generate an inhomogeneous network: start with a small number ofnodes, among them there is at least one type A node. At each step, a newtype A or B node is created with probability p or 1-p respectively. Itis added to the existing network by making m links with old nodes. Theconnection of newly created nodes to the old ones follows the preferentialattachment: a link is attached to node i with the probability . The is increased by 1 if site i is pointed by another newlycreated node. Each node is assigned with an initial connectivity to endow each B node with the chance to be connected by type A nodes.Thescaling-free feature is reserved in this inhomogeneous network. Theprobability P(k) that a node has k incoming links follows a power law: . Using the mean-field theory, one can show that [10]. The centralization C is used to measure the centrality quantitatively [11]. It's defined as , where is the highest connectivity of all nodes inthe network, is the average connectivity of each node, and Gis the total number of nodes.
It has been calculated that the centralization index of the BA network isabout 0.0021, while the value of WWW is about 0.02, about 10 times largerthan that of BA model. In an inhomogeneous network, when p increases from0.1 to 1, the centralization changes from about 0.1 to the value of the BAmodel [10]. So that using inhomogeneous networks to study the stabilityof networks may reveal some characteristics of the real-life networks.
The strategy of the intentional attack is as follows: at each step we pickout the node which has the most links and remove it and its links from thenetwork. Then we measure the size of the largest cluster of the network andthe average size of the isolated clusters (clusters not connected with thelargest clusters). The fraction of the nodes removed, the size of thelargest cluster and the average size of the isolated clusters are denoted by , and respectively. A critical point is defined as afraction of nodes removed when the largest cluster becomes a finite fractionof the whole network. In this report we attack the network until .
FIG. 1. The change of of the BA network (open square) and theinhomogeneous network (solid square) under intentional attack, with m=4, G=10000, and p=0.1 in the inhomogeneous network.
Figure 1 shows the change of in the inhomogeneous model and the BAmodel under intentional attack. Both networks have the same size and averagelinks. The result clearly shows that, inhomogeneous networks are much morefragile under sabotages, the size of the largest cluster of theinhomogeneous network decreases much faster than the BA network. WWW andInternet networks have been simulated under intentional attack. It was foundthat they broke down more quickly than BA model [9]. So comparedwith the BA model, the inhomogeneous model describe the realistic networksbetter and is more promising to investigate the characteristics of them.
Figure 2 shows, with different values of p, the change of and thechange of during the attack. From FIG.2(a) one observes that as pdecreases from 0.9 to 0.1, fewer nodes are needed to be removed in order toreduce the largest cluster to a certain fraction of the origin network. changes in accordance with the break of largest cluster shown in FIG.2(b).With the increase of p, the maximum arrives later and the value graduallybecomes greater. That means the dominant, largest cluster becomes moredifficult to be destroyed and substituted by many smaller isolated ones.
FIG. 2. The change of and the change of under attack. Theinhomogeneity index of the networks is p=0.1, 0.3, 0.5, 0.7, and 0.9from the left to the right, G=10000 and m=3.
It has been revealed that when p increases from 0 to 1, the centralizationdecreases monotonously [10]. The centralization properly reflects thebehaviors of the inhomogeneous network under the attack. Figure 3 (blacksquare) shows the relation between the centralization and the fraction ofthe nodes to be removed intentionally when . The fractionremoved when reaches the maximum corresponds well with the fractionremoved when (see figure 3, the black square and black circle).At this point we can safely conclude that the network has reached thecritical point and crashed to fragments.
FIG. 3. The relation between the centralization and the fraction of thenetwork removed when (), with different p from 0.1 to0.9 (black square); the relation between the centralization and the fractionremoved when reaches its maximum(), whenp increases from 0.1to 0.9(black circle). The dot line shows the theoretical predict of with different centralizations.
Cohen and Erez et al. have reported a method to calculate the criticalfraction of nodes needed to be removed in the sabotage strategy to disruptthe network [13,14]. The following summarize their deductions. Ifthere is a child network whose size is proportional to the whole network, itsatisfies [13]
, (1)
where is the average links of node i given that it is connected to node j, and is the conditional probability that node i has connectivity , giventhat it is connected to node j. Since ,for randomconnected networks [13]
. (2)
Insert into (1) we obtain
, (3)
where means the averages taken overall nodes of the network. At the critical point . If a fraction of nodes are randomly removed, the new connectivity distribution will be [13]
. (4)
After the removal of nodes, we obtain[13], , where and are the values of the original network. Insert theminto (3) we obtain[13]
. (5)
So that one gets from equation (5). For scale-free networks, where , we obtain[13]
, (6)
where K and are the maximal and minimal links of a node respectively. Ifthe attack is intentional, it has the fallowing two effects. (a) The cutoffconnectivity K reduces to some new value [14]: Because ,when , can be obtained approximately by replacingthe sum with an integral [14]
. (7)
(b) A random removal of links from the remaining nodes: links that haveconnected the removed nodes with the remaining nodes. The ratio of theselinks to the total links is [14]. Neglecting K and using thecontinuous approximation, we obtain[14]
. (8)
Randomly removing a fraction of links equals to randomly removing a fractionof nodes. So the network after attack is equivalent to a scale-free networkwith cutoff that has undergone random removal of a fraction of its nodes. Using (5)-(8), with and replacing and K, we obtain[14]
, (9)
where is the minimal connectivity.
Because most of the links are owned by type A nodes, the scale-freedistribution is only suitable for type Anodes. The calculated above is only the fraction of type A nodes. Sothe real should be
, (10)
where is obtained by solving equation (9). We find thatwhen p increases from 0.1 to 1, the change of the critical point has thesame tendency with the fraction of sites needed to remove to make thelargest cluster become 1% of the original network. (see FIG. 3, the blacksquare and the dot line) The integral deviation of these two curves resultsfrom the different criterions of the network's destruction. At the criticalpoint calculated theoretically the largest cluster of the network has becomeonly one thousandth of the original network.
In summary, because of the different rules used to create networks, theinhomogeneous network is more sensitive to sabotage than the BA network.With the study of the largest cluster and the average size of the isolatedclusters, the centralization of a network is found to properly describe howa network is centralized quantitatively. So the centralization is animportant parameter of the scale-free network. We also point out that themethod used to calculate the critical point of networks without diversity ofnodes and connections can also be used in the inhomogeneous network aftersome adjustment.
Acknowledgement
The work is supported by the Taizhao Foundation; Lin thanks Taizhao Foundation for support. Lin also thanks Prof. Qi Ouyang for direction and Xiang Cheng et al. for helpful discussions.
Reference
[1] Faloutsos M, Faloutsos P, and Faloutsos C1999 Comput. Commun. Rev. 29 251
[2] Huberman B A and Adamic L A 1999 Nature 401131
[3] Watts D J and Strogatz S H 1998 Nature 393 440
[4] Redner S 1998 Eur. Phys. J. B 4 131
[5] Jeong H, Tombor B, Oltvai Z N, and Barabasi A L 2000 Nature 407651
[6] Jeong H, Mason S P, Barabasi A L, and Oltvai Z N 2001 Nature 411 41
[7] Erdos P and Renyi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[8] Barabasi A L and Albert R 1999 Science 286 509
[9] Albert R, Jeong H and Barabasi A L 2000 Nature 406 378
[10] Cheng X, Wang H and Ouyang Q 2002 Phys. Rev. E 65 066115
[11] Wasserman S and Faust K 1994 Social Network Analysis (Cambridge University Press, Cambridge)
[12] Albert Rand Barabasi AL 2002Reviews of Modern Physics 74 47
[13] Cohen R, Erez K, ben-Avraham D, and Havlin S 2000 Phys. Rev. Lett. 85 4626
[14] Cohen R, Erez K, ben-Avraham D, and Havlin S 2001 Phys. Rev. Lett. 86 3682
作者简介：
林国基，男，物理系99级本科生。2001年11月获得泰兆奖助金的资助并进入北京大学非线性科学及生物技术实验室开展科研工作，指导老师为物理学院的欧阳颀教授。在过去的一年里，前期主要研究复杂性网络的性质，重点放在scale－free网络在蓄意攻击下的解体，完成了以上的论文并将在“中国物理快报”上发表；后期则主要进行斑图动力学课题的研究工作，重点是利用计算机模拟螺旋波的失稳行为，并与实验现象比较，找出螺旋波失稳的机理。该工作仍然在进行之中。
感悟与寄语：
在一年的工作中我最深刻的体会就是科研工作远不是以前想象的那么浪漫和轻松，它更多的是要求科研工作者有丰富的创造性和坚忍不拔的精神。每一个新的想法，每一个有意义的结果都是不断思考、不断创造的结果，每前进一步都要付出相当的劳动和汗水。
指导教师简介：
欧阳颀教授是物理学院长江计划特聘教授，一直从事非线性科学的基础理论与实验研究，主要研究方向是非线性动力学中的斑图自组织行为，被国际同行公认为斑图动力学领域的实验科学带头人之一。近年来开始从事生物技术方面的研究，取得了显著成果。
1