复旦大学：《网络科学导论 Introduction to Network Science》教学参考文献_Emergence of scaling in random networks

REPORTS Co/STO/LSMO that proposed to explain, in terms of sp-d bond- down to about 5% at 300 K in Co/STO/ ing, the positive polarization at the Co-ALO LSMO(4). However, other types of oxides of nterface(8). However, there is no general the- the double-perovskite family (for example, ory predicting the trend of the experimental Sr, FeMoO combine electronic properties results for Cothat is, a negative polarization similar to those of manganites with a defi with oxides of d elements (STO, CLO, Ta, O5) nitely higher Curie temperature(15).Their and a positive one when there are only s and p use in magnetic tunnel junctions is promising states(ALO). It is likely that the spin polariza- for a new generation of tunnel junctions with tion should also depend on the position of the very high magnetoresistance for room-tem- Fermi level with respect to the electronic levels perature applications. of each character above and below the gap of References and CoIALO/STO/LSMO wave in an insulator is a bloch wave with an 1.J S Moodera, L R Kinder, T M Wong. R Meservey, imaginary wave vector, one can expect differ Boeck, Science 281, 357( 1998) ent decay lengths for Bloch waves of different 3. M. Sharma, S.X. Wang. J H Nickel Phys. Rev. Lett. 82616(1999 4. J. M. De Teresa et al, ibid., P. 4288. rier, as illustrated by the calculations of mac- Laren et al. for Fe/ZnSe/Fe junctions(14) 238,173(1994) 6. M. B Stearns, J. Magn. Magn. Mater. 5. 187(1997). The influence of the barrier on the spin 7.)A. Hertz and K Aoi, Phys. Rev. 88, 3252(1973) m::2“b Fig 3. Bias dependence of the TMR ratio in(A) electrons and probing the fine structure of the Phys. Lett. 73, 698(19%ees,E Petroff, AFert, Appl Co/STO/LSMO and( B)Co/ALO/STO/LSMo d-DOS, as in Fig 3A. The DOS of a d-band can11.JSMooder unnel junctions. by introduction of virtual bound states)to pro- level of LSMO is situated above the Fermi duce specific bias dependencies. Although here 14. J M. MacLaren, X G. Zhang. W.H. Butler, X. Wang. level of Co and a maximum of inverse TMr we concentrated on the problem of the spin 15. k.Y. koba ash,, T. Kimura. H, sawada, K. Terakura. Y o proximately at the maximum of the spin the strongly spin-polarized LSMO only as a 16. We thank the group of A Revcoleschi for providing OS of Co. This is consistent with the max- useful spin analyzer, the large TMR ratios ob- LSMO targets, R. Lyonnet ar or Co/STO/LSMO junctions(Fig. 3A). For a (50% with a sto barrier )are also an interesting Energy and Industrial Technology Development Or positive bias, the TMR is expected to change result. The drawback arising from the low sign and become normal above 1 V when the Curie temperature of LSMO(350 K)is the Fermi level of LSMo goes down into the reduction of the TMR at room temperature, 1 July 1999 accepted 2 September 1999 energy range of the majority spin d-band of Co. This is also observed in Fig. 3A For ALO and ALO/STO barriers, a predom- inant tunneling of s-character electrons(see ar Emergence of Scaling in row in Fig. 2B)is the usual explanation of the positive polarization (6-8). The rapid drop Random Networks with bias(Fig. 3B) is similar to what has been observed in most junctions with ALO barriers, Albert-Laszlo Barabasi* and Reka Albert and completely different from what is obtained Systems as diverse as genetic networks or the world wide Web are best acter electrons(Fig. 3A). The origin of this described as networks with complex topology. A common property of many apid decrease of the TMR at relatively small large networks is that the vertex connectivities follow a scale-free power-law bias has never been clearly explained. This is distribution. This feature was found to be a consequence of two generic mech roughly consistent with the energy dependence anisms:() networks expand continuously by the addition of new vertices, and of the Dos induced by sp-d bonding effects on (i) new vertices attach preferentially to sites that are already well connected the first atomic layer of ALO in the calculation A model based on these two ingredients reproduces the observed stationary of Nguyen-Mahn et al.(8)for the Co-ALO scale-free distributions, which indicates that the development of large networks interface. But Zhang et al. (13) have also shov is governed by robust self-organizing phenomena that go beyond the particulars that a large part of the TMr drop can be of the individual systems. tributed to the excitation of spin waves. The experiments reported here and in sev- The inability of contemporary science to de- actions currently limits advances in eral recent publications (3, 4) demonstrate the scribe systems composed of nonidentical el- disciplines, ranging from molecular bi important role of the electronic structure of the ements that have diverse and nonlocal inter- to computer science (1). The difficul metal-oxide interface in determining the spin describing these systems lies partly in polarization of the tunneling electrons. The neg- Department of Physics, University of Notre Dame, topology: Many of them form rather complex ative polarization for the Co-STO interface has Notre Dame, IN 46556,USA. networks whose vertices are the elements of been ascribed to d-d bonding effects between " To whom correspondence should be addressed. E- the system and whose edges represent the Al and Ti(4). This interpretation is similar to mail: abend.edu interactions between them. For example, liy wsciencemag. org SCIENCE VOL 286 15 OCTOBER 1999

level of LSMO is situated above the Fermi level of Co and a maximum of inverse TMR is expected when the Fermi level of LSMO is approximately at the maximum of the spin 2 DOS of Co. This is consistent with the max￾imum of inverse TMR observed at 20.4 V for Co/STO/LSMO junctions (Fig. 3A). For a positive bias, the TMR is expected to change sign and become normal above 1 V when the Fermi level of LSMO goes down into the energy range of the majority spin d-band of Co. This is also observed in Fig. 3A. For ALO and ALO/STO barriers, a predom￾inant tunneling of s-character electrons (see ar￾row in Fig. 2B) is the usual explanation of the positive polarization (6–8). The rapid drop with bias (Fig. 3B) is similar to what has been observed in most junctions with ALO barriers, and completely different from what is obtained when the tunneling is predominantly by d-char￾acter electrons (Fig. 3A). The origin of this rapid decrease of the TMR at relatively small bias has never been clearly explained. This is roughly consistent with the energy dependence of the DOS induced by sp-d bonding effects on the first atomic layer of ALO in the calculation of Nguyen-Mahn et al. (8) for the Co-ALO interface. But Zhang et al. (13) have also shown that a large part of the TMR drop can be attributed to the excitation of spin waves. The experiments reported here and in sev￾eral recent publications (3, 4) demonstrate the important role of the electronic structure of the metal-oxide interface in determining the spin polarization of the tunneling electrons. The neg￾ative polarization for the Co-STO interface has been ascribed to d-d bonding effects between Al and Ti (4). This interpretation is similar to that proposed to explain, in terms of sp-d bond￾ing, the positive polarization at the Co-ALO interface (8). However, there is no general the￾ory predicting the trend of the experimental results for Co—that is, a negative polarization with oxides of d elements (STO, CLO, Ta2O5) and a positive one when there are only s and p states (ALO). It is likely that the spin polariza￾tion should also depend on the position of the Fermi level with respect to the electronic levels of each character above and below the gap of the insulator. In addition, as an evanescent wave in an insulator is a Bloch wave with an imaginary wave vector, one can expect differ￾ent decay lengths for Bloch waves of different character. This means that the final polarization could also depend on the thickness of the bar￾rier, as illustrated by the calculations of Mac￾Laren et al. for Fe/ZnSe/Fe junctions (14). The influence of the barrier on the spin polarization opens new ways to shape and op￾timize the TMR. Interesting bias dependencies can be obtained with barriers selecting the d electrons and probing the fine structure of the d-DOS, as in Fig. 3A. The DOS of a d-band can also be easily tailored by alloying (for example, by introduction of virtual bound states) to pro￾duce specific bias dependencies. Although here we concentrated on the problem of the spin polarization of the Co electrode and regarded the strongly spin-polarized LSMO only as a useful spin analyzer, the large TMR ratios ob￾tained by combining Co and LSMO electrodes (50% with a STO barrier) are also an interesting result. The drawback arising from the low Curie temperature of LSMO (;350 K) is the reduction of the TMR at room temperature, down to about 5% at 300 K in Co/STO/ LSMO (4). However, other types of oxides of the double-perovskite family (for example, Sr2FeMoO6) combine electronic properties similar to those of manganites with a defi￾nitely higher Curie temperature (15). Their use in magnetic tunnel junctions is promising for a new generation of tunnel junctions with very high magnetoresistance for room-tem￾perature applications. References and Notes 1. J. S. Moodera, L. R. Kinder, T. M. Wong, R. Meservey, Phys. Rev. Lett. 74, 3273 (1995). 2. J. De Boeck, Science 281, 357 (1998). 3. M. Sharma, S. X. Wang, J. H. Nickel, Phys. Rev. Lett. 82, 616 (1999). 4. J. M. De Teresa et al., ibid., p. 4288. 5. P. M. Tedrow and R. Meservey, Phys. Rev. B 7, 318 (1973); R. Meservey and P. M. Tedrow, Phys. Rep. 238, 173 (1994). 6. M. B. Stearns, J. Magn. Magn. Mater. 5, 187 (1997). 7. J. A. Hertz and K. Aoi, Phys. Rev. B 8, 3252 (1973). 8. D. Nguyen-Mahn et al., Mat. Res. Soc. Symp. Proc. 492, 319 (1998). 9. J. H. Park et al., Nature 392, 794 (1998). 10. J. Nassar, M. Hehn, A. Vaure`s, F. Petroff, A. Fert, Appl. Phys. Lett. 73, 698 (1998). 11. J. S. Moodera et al., ibid. 81, 1953 (1998). 12. K. Wang, thesis, New York University (1999). 13. S. Zhang, P. M. Levy, A. C. Marley, S. S. P. Parkin, Phys. Rev. Lett. 79, 3744 (1997). 14. J. M. MacLaren, X. G. Zhang, W. H. Butler, X. Wang, Phys. Rev. B 59, 5470 (1999). 15. K. I. Kobayashi, T. Kimura, H. Sawada, K. Terakura, Y. Tokura, Nature 395, 677 (1998). 16. We thank the group of A. Revcoleschi for providing LSMO targets, R. Lyonnet and A. Vaures for their experimental help and J. Nassar for fruitful discus￾sions. Supported by the European Union and the New Energy and Industrial Technology Development Or￾ganization of Japan. 1 July 1999; accepted 2 September 1999 Emergence of Scaling in Random Networks Albert-La´szlo´ Baraba´si* and Re´ka Albert Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mech￾anisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems. The inability of contemporary science to de￾scribe systems composed of nonidentical el￾ements that have diverse and nonlocal inter￾actions currently limits advances in many disciplines, ranging from molecular biology to computer science (1). The difficulty of describing these systems lies partly in their topology: Many of them form rather complex networks whose vertices are the elements of the system and whose edges represent the interactions between them. For example, liv￾Department of Physics, University of Notre Dame, Notre Dame, IN 46556, USA. *To whom correspondence should be addressed. E￾mail: alb@nd.edu Fig. 3. Bias dependence of the TMR ratio in (A) Co/STO/LSMO and (B) Co/ALO/STO/LSMO tunnel junctions. R EPORTS www.sciencemag.org SCIENCE VOL 286 15 OCTOBER 1999 509

REPORTS ing systems form a huge genetic network these two ingredients, we show that they are cited in a paper. Recently Redner(In)has whose vertices are proteins and genes, the responsible for the power-law scaling ob- shown that the probability that a paper is chemical interactions between them repre- served in real networks. Finally, we argue cited k times (representing the connectivity of nting edges(2). At a different organization- that these ingredients play an easily identifi- a paper within the network) follows a power al level, a large network is formed by the able and important role in the formation of law with exponent Yite=3. nervous system, whose vertices are the nerve many complex systems, which implies that The above examples (12)demo cells, connected by axons (3). But equally our results are relevant to a large class of many large random networks share complex networks occur in social science, networks observed in nature. mon feature that the distribution of their local where vertices are individuals or organiza- ouge there arks meatal d 'stems icat oaw nect viry es k we th sale, forewing acpower between them(4), or in the World Wide Web data is available for only a few. The collab- 2.1 and 4, which is unexpected within the (WWW), whose vertices are HTML docu- oration graph of movie actors represents a framework of the existing network models. ments connected by links pointing from one well-documented example of a social net- The random graph model of ER(7)assumes page to another (5, 6). Because of their large work. Each actor is represented by a vertex, that we start with N vertices and connect each ize and the complexity of their interactions, two actors being connected if they were cast pair of vertices with probability p. In the the topology of these networks is largely together in the same movie. The probability model, the probability that a vertex has k unknown that an actor has k links(characterizing his or edges follows a Poisson distribution P(k) Traditionally, networks of complex topol- her popularity) has a power-law tail for large e-x/kL, where ogy have been described with the random k, following P()k- Yalor, where Facto N-1 graph theory of Erdos and Renyi(ER)(7), 2.3 + 0.1(Fig. 1A). A more complex net but in the absence of data on large networks, work with over 800 million vertices(8)is the the predictions of the Er theory were rarely www, where a vertex is a document and the tested in the real world. However, driven by edges are the links pointing from one docu- In the small-world model recently intro- the computerization of data acquisition, such ment to another. The topology of this graph duced by Watts and Strogatz (WS)(10), N topological information is increasingly avail- determines the Web's connectivity and, con- vertices form a one-dimensional lattice, able, raising the possibility of understanding sequently, our effectiveness in locating infor- each vertex being connected to its two the dynamical and topological stability of mation on the www(5). Information about nearest and next-nearest neighbors. With large networks. P(h)can be obtained using robots(6), indi- probability p, each edge is reconnected to a Here we report on the existence of a high cating that the probability that k documents vertex chosen at random. The long-range degree of self-organization characterizing the point to a certain Web page follows a power connections generated by this process de large-scale properties of complex networks. law, with y 2.1 +0.1(Fig. IB)(9).A crease the distance between the vertices, Exploring several large databases describing network whose topology reflects the histori- leading to a small-world phenomenon(13). the topology of large networks that span cal patterns of urban and industrial develop- often referred to as six degrees of separa- fields as diverse as the www or citation ment is the electrical power grid of the west- tion(14). For p = 0, the probability distri constituents, the probability P(h) that a ver- edges being to the high-voltage transmission the lattice: whereas for finite p, P() still tex in the network interacts with k other lines between them (10). Because of the rel- peaks around z, but it gets broader(15).A vertices decays as a power law, following atively modest size of the network, contain- common feature of the er and ws models P(k)k. This result indicates that large ing only 4941 vertices, the scaling region is is that the probability of finding a highly networks self-organize into a scale-free state, less prominent but is nevertheless approxi- connected vertex(that is, a large k)decreas- a feature unpredicted by all existing random mated by a power law with an exponent es exponentially with k; thus, vertices with scale invariance, we show that existing net- complex network is formed by the citation contrast, the power-law tail characterizing work models fail to incorporate growth and patterns of the scientific publications, the ver- P() for the networks studied indicates that preferential attachment, two key features of tices being papers published in refereed jour- highly connected (large k) vertices have a real networks. Using a model incorporating nals and the edges being links to the articles large chance of occurring, dominating the 10° A works that are not incorporated in these mod- els. First, both models assume that we start with a fixed number(N of vertices that ar then randomly connected(ER model), or re connected (wS model), without modifying N. In contrast, most real world networks are pen and they form by the continuous add ion of new vertices to the system, thus the number of vertices N increases throughout the lifetime of the network. For example, the actor network grows by the addition of new actors to the system, the www grows expo- 2计=3412时299+(278( ed lines have constantly g0 ws by the publication of 3,(B) papers. Consequently, a common feature of 15 OCTOBER 1999 VOL 286 SCIENCE www

ing systems form a huge genetic network whose vertices are proteins and genes, the chemical interactions between them repre￾senting edges (2). At a different organization￾al level, a large network is formed by the nervous system, whose vertices are the nerve cells, connected by axons (3). But equally complex networks occur in social science, where vertices are individuals or organiza￾tions and the edges are the social interactions between them (4), or in the World Wide Web (WWW), whose vertices are HTML docu￾ments connected by links pointing from one page to another (5, 6). Because of their large size and the complexity of their interactions, the topology of these networks is largely unknown. Traditionally, networks of complex topol￾ogy have been described with the random graph theory of Erdo˝s and Re´nyi (ER) (7), but in the absence of data on large networks, the predictions of the ER theory were rarely tested in the real world. However, driven by the computerization of data acquisition, such topological information is increasingly avail￾able, raising the possibility of understanding the dynamical and topological stability of large networks. Here we report on the existence of a high degree of self-organization characterizing the large-scale properties of complex networks. Exploring several large databases describing the topology of large networks that span fields as diverse as the WWW or citation patterns in science, we show that, indepen￾dent of the system and the identity of its constituents, the probability P(k) that a ver￾tex in the network interacts with k other vertices decays as a power law, following P(k) ; k2g. This result indicates that large networks self-organize into a scale-free state, a feature unpredicted by all existing random network models. To explain the origin of this scale invariance, we show that existing net￾work models fail to incorporate growth and preferential attachment, two key features of real networks. Using a model incorporating these two ingredients, we show that they are responsible for the power-law scaling ob￾served in real networks. Finally, we argue that these ingredients play an easily identifi￾able and important role in the formation of many complex systems, which implies that our results are relevant to a large class of networks observed in nature. Although there are many systems that form complex networks, detailed topological data is available for only a few. The collab￾oration graph of movie actors represents a well-documented example of a social net￾work. Each actor is represented by a vertex, two actors being connected if they were cast together in the same movie. The probability that an actor has k links (characterizing his or her popularity) has a power-law tail for large k, following P(k) ; k2gactor, where gactor 5 2.3 6 0.1 (Fig. 1A). A more complex net￾work with over 800 million vertices (8) is the WWW, where a vertex is a document and the edges are the links pointing from one docu￾ment to another. The topology of this graph determines the Web’s connectivity and, con￾sequently, our effectiveness in locating infor￾mation on the WWW (5). Information about P(k) can be obtained using robots (6), indi￾cating that the probability that k documents point to a certain Web page follows a power law, with gwww 5 2.1 6 0.1 (Fig. 1B) (9). A network whose topology reflects the histori￾cal patterns of urban and industrial develop￾ment is the electrical power grid of the west￾ern United States, the vertices being genera￾tors, transformers, and substations and the edges being to the high-voltage transmission lines between them (10). Because of the rel￾atively modest size of the network, contain￾ing only 4941 vertices, the scaling region is less prominent but is nevertheless approxi￾mated by a power law with an exponent gpower . 4 (Fig. 1C). Finally, a rather large complex network is formed by the citation patterns of the scientific publications, the ver￾tices being papers published in refereed jour￾nals and the edges being links to the articles cited in a paper. Recently Redner (11) has shown that the probability that a paper is cited k times (representing the connectivity of a paper within the network) follows a power law with exponent gcite 5 3. The above examples (12) demonstrate that many large random networks share the com￾mon feature that the distribution of their local connectivity is free of scale, following a power law for large k with an exponent g between 2.1 and 4, which is unexpected within the framework of the existing network models. The random graph model of ER (7) assumes that we start with N vertices and connect each pair of vertices with probability p. In the model, the probability that a vertex has k edges follows a Poisson distribution P(k) 5 e2llk /k!, where l 5 NS N 2 1 k D pk ~1 2 p! N212k In the small-world model recently intro￾duced by Watts and Strogatz (WS) (10), N vertices form a one-dimensional lattice, each vertex being connected to its two nearest and next-nearest neighbors. With probability p, each edge is reconnected to a vertex chosen at random. The long-range connections generated by this process de￾crease the distance between the vertices, leading to a small-world phenomenon (13), often referred to as six degrees of separa￾tion (14). For p 5 0, the probability distri￾bution of the connectivities is P(k) 5 d(k 2 z), where z is the coordination number in the lattice; whereas for finite p, P(k) still peaks around z, but it gets broader (15). A common feature of the ER and WS models is that the probability of finding a highly connected vertex (that is, a large k) decreas￾es exponentially with k; thus, vertices with large connectivity are practically absent. In contrast, the power-law tail characterizing P(k) for the networks studied indicates that highly connected (large k) vertices have a large chance of occurring, dominating the connectivity. There are two generic aspects of real net￾works that are not incorporated in these mod￾els. First, both models assume that we start with a fixed number (N) of vertices that are then randomly connected (ER model), or re￾connected (WS model), without modifying N. In contrast, most real world networks are open and they form by the continuous addi￾tion of new vertices to the system, thus the number of vertices N increases throughout the lifetime of the network. For example, the actor network grows by the addition of new actors to the system, the WWW grows expo￾nentially over time by the addition of new Web pages (8), and the research literature constantly grows by the publication of new papers. Consequently, a common feature of Fig. 1. The distribution function of connectivities for various large networks. (A) Actor collaboration graph with N 5 212,250 vertices and average connectivity ^k& 5 28.78. (B) WWW, N 5 325,729, ^k& 5 5.46 (6). (C) Power grid data, N 5 4941, ^k& 5 2.67. The dashed lines have slopes (A) gactor 5 2.3, (B) gwww 5 2.1 and (C) gpower 5 4. R EPORTS 510 15 OCTOBER 1999 VOL 286 SCIENCE www.sciencemag.org

REPORTS these systems is that the network continuous- that a new vertex is connected with equal m-1/k)=l-mt/k-(I+ mo). The prob- ly expands by the addition of new vertices probability to any vertex in the system [that ability density P(k)can be obtained from hat are connected to the vertices already is, II(k)=const=1/(m )]. Such P(k)= aP[k, (1)<k/ak, which over long present in the systen a model (Fig. 2B) leads to P(k)- time periods leads to the stationary solution Second, the random network models exp(-Bk), indicating that the absence of sume that the probability that two vertices are preferential attachment eliminates connected is random and uniform. In con- free feature of the distribution. In P(k)= trast, most real networks exhibit preferential we start with N vertices and no edges. At giving y= 3, independent of m. Although it connectivity. For example, a new actor is each time step, we randomly select a vertex reproduces the observed scale-free distribu- most likely to be cast in a supporting role and connect it with probability ll(k )=k,/ tion, the proposed model cannot be expected with more established and better-known ac- 2,k, to vertex i in the system. Although at to account for all aspects of the studied net tors. Consequently, the probability that a new early times the model exhibits power-law works. For that, we need to model these actor will be cast with an established one is scaling, P(k)is not stationary: because N is systems in more detail. For example, in the luch higher than that the new actor will be constant and the number of edges increases model we assumed linear preferential attach ast with other less-known actors. Similarly, with time, after T=N time steps the system ment; that is, II(k)k. However, although a newly created Web page will be more likely reaches a state in which all vertices are con- in general ll() could have an arbitrary non- to include links to well-known popular doc- nected. The failure of models A and B indi- linear form ll(k)- k, simulations indicate uments with already-high connectivity, and a cates that both ingredients-growth and pref- that scaling is present only for a= 1. Fur- new manuscript is more likely to cite a well- erential attachment-are needed for the de- thermore, the exponents obtained for the dif- known and thus much-cited paper than its velopment of the stationary power-law distri- ferent networks are scattered between 2. 1 and less-cited and consequently less-known peer. bution observed in Fig. 1 4. However, it is easy to modify our model to These examples indicate that the probability Because of the preferential attachment, a account for exponents different from y= 3 with which a new vertex connects to the vertex that acquires more connections than For example, if we assume that a fraction p of existing vertices is not uniform; there is a another one will increase its connectivity at a the links is directed, we obtain y(p)= 3 higher probability that it will be linked to a higher rate; thus, an initial difference in the p, which is supported by numerical simula vertex that already has a large number of connectivity between two vertices will in- tions(16). Finally, some networks evolve not connections crease further as the network grows. The rate only by adding new vertices but by adding We next show that a model based on these at which a vertex acquires edges is ak /ar nd sometimes removing) connections be- two ingredients naturally leads to the ob- k, /21, which gives k n)= m(t/t,)., where tween established vertices. Although these scale-invariant distribution. To incor- Ii is the time at which vertex i was added to and other system-specific features coul the growing character of the network, the system(see Fig. 2C), a scaling property modify the exponent y, our model offers the with a small number (mo)of vertices, that could be directly tested once time-re- first successful mechanism accounting for the at every time step we add a new vertex with solved data on network connectivity becomes scale-invariant nature of real networks. (Smo)edges that link the new vertex to m available. Thus older(with smaller 4) verti- Growth and preferential attachment are different vertices already present in the sys- ces increase their connectivity at the expense mechanisms common to a number of com tem. To incorporate preferential attachment, of the younger(with larger I; )ones, leading plex systems, including business networks ye assume that the probability Il that a new over time to some vertices that are highly (17, 18). social networks(describing individ vertex will be connected to vertex i depends connected, a"rich-get-richer"phenomenon uals or organizations), transportation net on the connectivity k, of that vertex, so that that can be easily detected in real networks. works(19), and so on. Consequently, we n(ki)=k/2,k After I time steps, the Furthermore, this property can be used to expect that the scale-invariant state observed model leads to a random network with /+ calculate y analytically. The probability that in all systems for which detailed data has vertices and mt edges. This network a vertex i has a connectivity smaller than k, been available to us is a generic property of evolves into a scale-invariant state with the P[(0< k] can be written as P(l, many complex networks, with applicability probability that a vertex has k edges, follow- m2t/k2). Assuming that we add the vertices reaching far beyond the quoted examples. a ing a power law with an exponent model- to the system at equal time intervals, we better description of these systems would 2.9+ 0.1(Fig 2A). Because the power law obtain P(, m2t/k)=1-P(, s help in understanding other complex systems observed for real networks describes systems of rather different sizes at different stages of their development, it is expected that a cor rect model should provide a distribution A B whose main features are independent of time. Indeed, as Fig. 2A demonstrates, P(k)is independent of time(and subsequently inde- pendent of the system size mo +1), indicat- 104 ing that despite its continuous growth, the system organizes itself into a scale-free sta tionary state. ing in the model indicates that growth and 10 1 o oto obbo 10 b% 1o"" o"To 1o in network development. To verify that both ingredients are necessary, we investigated Fig. 2. (A)The power-law connectivity distribution at t= 150,000(O)and t=200,000(Q)as btained from the model, using mo =m= 5. The slope of the dashed line is y=2.9.( B)The two variants of the model. Model A keeps the exponential connectivity distribution for model A, in the case o mo of thec 1(O), mo =m growing character of the network, but prefer ential attachment is eliminated by assuming vertices added to the system at t,=5 and t2=95. The dashed line has slope 0.5 wsciencemag. org SCIENCE VOL 286 15 OCTOBER 1999 511

these systems is that the network continuous￾ly expands by the addition of new vertices that are connected to the vertices already present in the system. Second, the random network models as￾sume that the probability that two vertices are connected is random and uniform. In con￾trast, most real networks exhibit preferential connectivity. For example, a new actor is most likely to be cast in a supporting role with more established and better-known ac￾tors. Consequently, the probability that a new actor will be cast with an established one is much higher than that the new actor will be cast with other less-known actors. Similarly, a newly created Web page will be more likely to include links to well-known popular doc￾uments with already-high connectivity, and a new manuscript is more likely to cite a well￾known and thus much-cited paper than its less-cited and consequently less-known peer. These examples indicate that the probability with which a new vertex connects to the existing vertices is not uniform; there is a higher probability that it will be linked to a vertex that already has a large number of connections. We next show that a model based on these two ingredients naturally leads to the ob￾served scale-invariant distribution. To incor￾porate the growing character of the network, starting with a small number (m0 ) of vertices, at every time step we add a new vertex with m(#m0 ) edges that link the new vertex to m different vertices already present in the sys￾tem. To incorporate preferential attachment, we assume that the probability P that a new vertex will be connected to vertex i depends on the connectivity ki of that vertex, so that P(ki ) 5 ki /Sj kj . After t time steps, the model leads to a random network with t 1 m0 vertices and mt edges. This network evolves into a scale-invariant state with the probability that a vertex has k edges, follow￾ing a power law with an exponent gmodel 5 2.9 6 0.1 (Fig. 2A). Because the power law observed for real networks describes systems of rather different sizes at different stages of their development, it is expected that a cor￾rect model should provide a distribution whose main features are independent of time. Indeed, as Fig. 2A demonstrates, P(k) is independent of time (and subsequently inde￾pendent of the system size m0 1 t), indicat￾ing that despite its continuous growth, the system organizes itself into a scale-free sta￾tionary state. The development of the power-law scal￾ing in the model indicates that growth and preferential attachment play an important role in network development. To verify that both ingredients are necessary, we investigated two variants of the model. Model A keeps the growing character of the network, but prefer￾ential attachment is eliminated by assuming that a new vertex is connected with equal probability to any vertex in the system [that is, P(k) 5 const 5 1/(m0 1 t 2 1)]. Such a model (Fig. 2B) leads to P(k) ; exp(2bk), indicating that the absence of preferential attachment eliminates the scale￾free feature of the distribution. In model B, we start with N vertices and no edges. At each time step, we randomly select a vertex and connect it with probability P(ki ) 5 ki / Sj k j to vertex i in the system. Although at early times the model exhibits power-law scaling, P(k) is not stationary: because N is constant and the number of edges increases with time, after T . N2 time steps the system reaches a state in which all vertices are con￾nected. The failure of models A and B indi￾cates that both ingredients—growth and pref￾erential attachment—are needed for the de￾velopment of the stationary power-law distri￾bution observed in Fig. 1. Because of the preferential attachment, a vertex that acquires more connections than another one will increase its connectivity at a higher rate; thus, an initial difference in the connectivity between two vertices will in￾crease further as the network grows. The rate at which a vertex acquires edges is ]ki /]t 5 ki / 2t, which gives ki (t) 5 m(t/ti )0.5, where ti is the time at which vertex i was added to the system (see Fig. 2C), a scaling property that could be directly tested once time-re￾solved data on network connectivity becomes available. Thus older (with smaller ti ) verti￾ces increase their connectivity at the expense of the younger (with larger ti ) ones, leading over time to some vertices that are highly connected, a “rich-get-richer” phenomenon that can be easily detected in real networks. Furthermore, this property can be used to calculate g analytically. The probability that a vertex i has a connectivity smaller than k, P[ki (t) , k], can be written as P(ti . m2 t/k2 ). Assuming that we add the vertices to the system at equal time intervals, we obtain P(ti . m2 t/k2 ) 5 1 2 P(ti # m2 t/k2 ) 5 1 2 m2 t/k2 (t 1 m0). The prob￾ability density P(k) can be obtained from P(k) 5 ]P[ki (t) , k]/]k, which over long time periods leads to the stationary solution P~k! 5 2m2 k3 giving g 5 3, independent of m. Although it reproduces the observed scale-free distribu￾tion, the proposed model cannot be expected to account for all aspects of the studied net￾works. For that, we need to model these systems in more detail. For example, in the model we assumed linear preferential attach￾ment; that is, P(k) ; k. However, although in general P(k) could have an arbitrary non￾linear form P(k) ; ka, simulations indicate that scaling is present only for a 5 1. Fur￾thermore, the exponents obtained for the dif￾ferent networks are scattered between 2.1 and 4. However, it is easy to modify our model to account for exponents different from g 5 3. For example, if we assume that a fraction p of the links is directed, we obtain g( p) 5 3 2 p, which is supported by numerical simula￾tions (16). Finally, some networks evolve not only by adding new vertices but by adding (and sometimes removing) connections be￾tween established vertices. Although these and other system-specific features could modify the exponent g, our model offers the first successful mechanism accounting for the scale-invariant nature of real networks. Growth and preferential attachment are mechanisms common to a number of com￾plex systems, including business networks (17, 18), social networks (describing individ￾uals or organizations), transportation net￾works (19), and so on. Consequently, we expect that the scale-invariant state observed in all systems for which detailed data has been available to us is a generic property of many complex networks, with applicability reaching far beyond the quoted examples. A better description of these systems would help in understanding other complex systems Fig. 2. (A) The power-law connectivity distribution at t 5 150,000 (E) and t 5 200,000 (h) as obtained from the model, using m0 5 m 5 5. The slope of the dashed line is g 5 2.9. (B) The exponential connectivity distribution for model A, in the case of m0 5 m 5 1 (E), m0 5 m 5 3 (h), m0 5 m 5 5 ({), and m0 5 m 5 7 (‚). (C) Time evolution of the connectivity for two vertices added to the system at t1 5 5 and t2 5 95. The dashed line has slope 0.5. R EPORTS www.sciencemag.org SCIENCE VOL 286 15 OCTOBER 1999 511

REPORTS as well, for which less topological informa- References and notes iagramofacomputerchip(seehttp://vlsicad.cs. tion is currently available, including such 1. R. Gallagher and T. Appenzeller, Science 284. 79 ucla. edu/-cheese/ispd98. html). We foun important examples as genetic or signaling (1999):R. F. Service, ibid., P.80. 2. G. Weng, U. S Bhalla, R. lyengar, ibid, P. 92. networks in biological systems. We often do 3. C. Koch and G. Laurent, ibid. p.96. not think of biological systems as open or 4. 5. Wasserman and K Faust, Social Network ly coded. However, possible scale-free fea- 5 \ Cambridge Univ Press, Cambridge, 1994) growing, because their features are genetical vertices with over 200 edges have bee abers of the Clever project Sci. Am. 280, $4 13.5. Milgram, Psychol. Today 2, 60(1967): M. Kochen, ares of genetic and signaling networks could 6.R ALbert, H Jeong A.-LBarabasi, Nature 401 reflect the networks' evolutional 1999:A-L Barabasi, R. Albert, H. Jeong. Physica A 14. J. Guare, Six Degrees of Separation: A Play(Vintage dominated by growth and aggregation of dif- 272, 173(1999): seealsohttp:/ Books, New York, 1990). 15. M. Barthelemy and L A N. Amaral, Phys. Rev. Lett. networks, answers to these questions might Nature400.107(1999 not be too far away. Similar mechanisms 9. In addition to the distribution of incoming 18. Preferential attachment was also used to model could explain the origin of the social and www displays a number of other scale-fre economic disparities governing competitive systems, because the scale-free inhomogene Nature 401, 131(1999), the distribution of searches 19. 1. R. Banavar A Maritan, A Rinaldo, Nature 399, 130 1999 ities are the inevitable consequence of self- luk A. Huberman, P. L T. Pirolli, J. E. Pitkow, R. J. 20. We thank D ) Watts for providing the C elegans ar organization due to the local decisions made kose, Science 280, 95(1998), or the number of ks per Web page(6) power grid data, B C. Tjaden for supplying the actor data, H. Jeong for collecting the d the www by the individual vertices, based on informa- 10. D. J. Watts and S. H. Strogatz, Nature 393, 440 and L A. N. Amaral for helpful discussions. This wor tion that is biased toward the more visible 11. 5. Redner, Eur. Phys. 1.8 4, 131(1998) ally supported by NSF Career Award DMR- (richer) vertices, irrespective of the nature 12. We also studied the neural network of the worm and origin of this visibility caenorhabditis elega 10)and the benchmark 24 June 1999: accepted 2 September 1999 Osmium Isotope Constraints on suprasubduction xenolith locality, the Tubaf seamount in the Lihir island group of the Ore Metal Recycling in Tabar-Lihir-Tanga-Feni island arc in Papua New Guinea(ig. 1). This xenolith locality is Subduction zones o nportant for the following reasons:()it ntains samples that represent a complete section of oceanic lithosphere at an intraoce Brent L. A. Mcinnes, *Jannene S McBride,2 Noreen J. Evans, 1 nic convergent margin, (ii)it is located ad David D. Lambert 2 Anita S. Andrew 3 jacent to one of the world's largest and youngest volcano-hosted Au deposits, and Veined peridotite xenoliths from the mantle beneath the giant Ladolam gold (ii) it contains metasomatized mantle perido- deposit on Lihir Island, Papua New Guinea, are 2 to 800 times more enriched tite xenoliths with Au-enriched vein minerals in copper, gold, platinum, and palladium than surrounding depleted arc mantle that crystallized in the mantle from oxidizing, Gold ores have osmium isotope compositions similar to those of the underlying alkali-and sulfur-rich hydrous fluids. During the oceanographic investigation of mary origin of the metals was the mantle. Because the mantle is relatively submarine hydrothermal systems in Papua prerequisite for generating porphyry-epithermal copper-gold deposit be depleted in gold, copper, and palladium, tectonic processes that enhance the New Guinea (8), a submarine cinder cone advective transport and concentration of these fluid soluble metals ma (Tubaf volcano, 1280 m below sea level; 3o 15.25′S,152°32.50′E) was discovered14 km southwest of the giant Ladolam gold mine The tectonic relationship between subduction- to 87Os) is a tracer of metallogenic processes at (40 million oz contained Au) on Lihir Is related magmatism at convergent margins and convergent margins because both elements land. Dredge and video.grab sampling of the porphyry copper-gold(Cu-Au) ore formation have geochemical properties similar to metals I-km-diameter volcanic cone returned 130 has long been recognized (1). However, the that occur in porphyry ore its(2, 3). Be- ultramafic, mafic, and sedimentary xenoliths ysical and chemical processes that govern cause Re is highly concentrated in crustal rocks The study of these samples has provided ar Cu-Au metallogeny and the ultimate source(s) and Os is concentrated in the mantle( 4, 5), this unprecedented view of the source region of of the metals in these ore deposits are poorly isotopic system is particularly useful for quan- an island arc magmatic system with a propen understood. The rhenium-osmium(Re-Os)iso- tifying the flux of ore elements in island arc sity to produce giant porphyry-epithermal ore topic system(based on the B- decay of 8Re settings where the two principal reservoirs for deposits. The xenolith assemblage includes metals are subducted crust and mantle wedge spinel Lherzolite, harzburgite, websterite, or COmmonwealth Scientific and Industrial Research peridotite thopyroxenite, clinopyroxenite, syenite, ser Organization Exploration and Mining, Post Office Boy Os isotope studies in subduction zones are pentinite, gabbro, hornblende gabbro, dia 136, North Ryde, New South Wales 1670, Australia; currently limited because of the rarity of base, basalt, pelagic deep-sea sediment, and wealth deep-seated suprasubduction samples(rocks shallow-water volcaniclastic sediment as well cientific and Industrial Research Organization Petre overlying a subducted slab). Previous studies as coralline and coralgal limestone. These North Ryde (6, 7) have demonstrated that radiogenic Os lithologies represent a cross section of the su New South Wales 1670, Australia is introduced into the subarc mantle by hy- prasubduction assemblage and can be reassem- *To whom correspondence should be addressed. E- drous, oxidizing fluids derived during slab bled into an"ophiolite-type "model of ocea mail Brent. McInnes@dem. csiro dehydration. We report on results from a lithosphere(Fig. 1)(9 512 15OCtobeR1999Vol286ScieNcewww.sciencemag.org

as well, for which less topological informa￾tion is currently available, including such important examples as genetic or signaling networks in biological systems. We often do not think of biological systems as open or growing, because their features are genetical￾ly coded. However, possible scale-free fea￾tures of genetic and signaling networks could reflect the networks’ evolutionary history, dominated by growth and aggregation of dif￾ferent constituents, leading from simple mol￾ecules to complex organisms. With the fast advances being made in mapping out genetic networks, answers to these questions might not be too far away. Similar mechanisms could explain the origin of the social and economic disparities governing competitive systems, because the scale-free inhomogene￾ities are the inevitable consequence of self￾organization due to the local decisions made by the individual vertices, based on informa￾tion that is biased toward the more visible (richer) vertices, irrespective of the nature and origin of this visibility. References and Notes 1. R. Gallagher and T. Appenzeller, Science 284, 79 (1999); R. F. Service, ibid., p. 80. 2. G. Weng, U. S. Bhalla, R. Iyengar, ibid., p. 92. 3. C. Koch and G. Laurent, ibid., p. 96. 4. S. Wasserman and K. Faust, Social Network Analysis (Cambridge Univ. Press, Cambridge, 1994). 5. Members of the Clever project, Sci. Am. 280, 54 ( June 1999). 6. R. Albert, H. Jeong, A.-L. Baraba´si, Nature 401, 130 (1999); A.-L. Baraba´si, R. Albert, H. Jeong, Physica A 272, 173 (1999); see also http://www.nd.edu/~net￾works. 7. P. Erdo˝s and A. Re´nyi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960); B. Bolloba´s, Random Graphs (Aca￾demic Press, London, 1985). 8. S. Lawrence and C. L. Giles, Science 280, 98 (1998); Nature 400, 107 (1999). 9. In addition to the distribution of incoming links, the WWW displays a number of other scale-free features characterizing the organization of the Web pages within a domain [B. A. Huberman and L. A. Adamic, Nature 401, 131 (1999)], the distribution of searches [B. A. Huberman, P. L. T. Pirolli, J. E. Pitkow, R. J. Lukose, Science 280, 95 (1998)], or the number of links per Web page (6). 10. D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998). 11. S. Redner, Eur. Phys. J. B 4, 131 (1998). 12. We also studied the neural network of the worm Caenorhabditis elegans (3, 10) and the benchmark diagram of a computer chip (see http://vlsicad.cs. ucla.edu/;cheese/ispd98.html). We found that P(k) for both was consistent with power-law tails, despite the fact that for C. elegans the relatively small size of the system (306 vertices) severely limits the data quality, whereas for the wiring diagram of the chips, vertices with over 200 edges have been eliminated from the database. 13. S. Milgram, Psychol. Today 2, 60 (1967); M. Kochen, ed., The Small World (Ablex, Norwood, NJ, 1989). 14. J. Guare, Six Degrees of Separation: A Play ( Vintage Books, New York, 1990). 15. M. Barthe´le´my and L. A. N. Amaral, Phys. Rev. Lett. 82, 15 (1999). 16. For most networks, the connectivity m of the newly added vertices is not constant. However, choosing m randomly will not change the exponent g ( Y. Tu, personal communication). 17. W. B. Arthur, Science 284, 107 (1999). 18. Preferential attachment was also used to model evolving networks (L. A. N. Amaral and M. Bar￾the´le´my, personal communication). 19. J. R. Banavar, A. Maritan, A. Rinaldo, Nature 399, 130 (1999). 20. We thank D. J. Watts for providing the C. elegans and power grid data, B. C. Tjaden for supplying the actor data, H. Jeong for collecting the data on the WWW, and L. A. N. Amaral for helpful discussions. This work was partially supported by NSF Career Award DMR- 9710998. 24 June 1999; accepted 2 September 1999 Osmium Isotope Constraints on Ore Metal Recycling in Subduction Zones Brent I. A. McInnes,1 * Jannene S. McBride,2 Noreen J. Evans,1 David D. Lambert,2 Anita S. Andrew3 Veined peridotite xenoliths from the mantle beneath the giant Ladolam gold deposit on Lihir Island, Papua New Guinea, are 2 to 800 times more enriched in copper, gold, platinum, and palladium than surrounding depleted arc mantle. Gold ores have osmium isotope compositions similar to those of the underlying subduction-modified mantle peridotite source region, indicating that the pri￾mary origin of the metals was the mantle. Because the mantle is relatively depleted in gold, copper, and palladium, tectonic processes that enhance the advective transport and concentration of these fluid soluble metals may be a prerequisite for generating porphyry-epithermal copper-gold deposits. The tectonic relationship between subduction￾related magmatism at convergent margins and porphyry copper-gold (Cu-Au) ore formation has long been recognized (1). However, the physical and chemical processes that govern Cu-Au metallogeny and the ultimate source(s) of the metals in these ore deposits are poorly understood. The rhenium-osmium (Re-Os) iso￾topic system (based on the b2 decay of 187Re to 187Os) is a tracer of metallogenic processes at convergent margins because both elements have geochemical properties similar to metals that occur in porphyry ore deposits (2, 3). Be￾cause Re is highly concentrated in crustal rocks and Os is concentrated in the mantle (4, 5), this isotopic system is particularly useful for quan￾tifying the flux of ore elements in island arc settings where the two principal reservoirs for metals are subducted crust and mantle wedge peridotite. Os isotope studies in subduction zones are currently limited because of the rarity of deep-seated suprasubduction samples (rocks overlying a subducted slab). Previous studies (6, 7) have demonstrated that radiogenic Os is introduced into the subarc mantle by hy￾drous, oxidizing fluids derived during slab dehydration. We report on results from a suprasubduction xenolith locality, the Tubaf seamount in the Lihir island group of the Tabar-Lihir-Tanga-Feni island arc in Papua New Guinea (Fig. 1). This xenolith locality is important for the following reasons: (i) it contains samples that represent a complete section of oceanic lithosphere at an intraoce￾anic convergent margin, (ii) it is located ad￾jacent to one of the world’s largest and youngest volcano-hosted Au deposits, and (iii) it contains metasomatized mantle perido￾tite xenoliths with Au-enriched vein minerals that crystallized in the mantle from oxidizing, alkali- and sulfur-rich hydrous fluids. During the oceanographic investigation of submarine hydrothermal systems in Papua New Guinea (8), a submarine cinder cone (Tubaf volcano, 1280 m below sea level; 3° 15.259 S, 152° 32.509 E) was discovered 14 km southwest of the giant Ladolam gold mine (.40 million oz contained Au) on Lihir Is￾land. Dredge and video-grab sampling of the 1-km-diameter volcanic cone returned 130 ultramafic, mafic, and sedimentary xenoliths. The study of these samples has provided an unprecedented view of the source region of an island arc magmatic system with a propen￾sity to produce giant porphyry-epithermal ore deposits. The xenolith assemblage includes spinel lherzolite, harzburgite, websterite, or￾thopyroxenite, clinopyroxenite, syenite, ser￾pentinite, gabbro, hornblende gabbro, dia￾base, basalt, pelagic deep-sea sediment, and shallow-water volcaniclastic sediment as well as coralline and coralgal limestone. These lithologies represent a cross section of the su￾prasubduction assemblage and can be reassem￾bled into an “ophiolite-type” model of oceanic lithosphere (Fig. 1) (9). 1 Commonwealth Scientific and Industrial Research Organization Exploration and Mining, Post Office Box 136, North Ryde, New South Wales 1670, Australia; 2 Department of Earth Sciences, Monash University, Clayton, Victoria 3168, Australia; 3 Commonwealth Scientific and Industrial Research Organization Petro￾leum Resources, Post Office Box 136, North Ryde, New South Wales 1670, Australia. *To whom correspondence should be addressed. E￾mail: Brent.McInnes@dem.csiro.au R EPORTS 512 15 OCTOBER 1999 VOL 286 SCIENCE www.sciencemag.org