PERSPECTIVE
Scale-Free Networks:A Decade and Beyond
Albert-LászlóBarabási
For decades,we tacitly assumed that the components of such complex systems as the cell,the society,
or the Internet are randomly wired together.In the past decade,an avalanche of research has shown that many real networks,independent of their age,function,and scope,converge to similar architectures,a universality that allowed researchers from different disciplines to embrace network theory as a common paradigm.The decade-old discovery of scale-free networks was one of those events that had helped catalyze the emergence of network science,a new research field with its distinct set of challenges and accomplishments.
N
ature,society,and many technologies are sustained by numerous networks that are not only too important to fail but
paradoxically for decades have also proved too complicated to understand.Simple models,like the one introduced in 1959by mathematicians Pál Erd ős and Alfréd Rényi (1),drove much of our thinking about interconnected systems.They assumed that complex systems are wired randomly together,a hypothesis that was adopted by so-ciology,biology,and computer science.It had considerable predictive power,explaining for ex-ample why everybody is only six handshakes from anybody else (2–5),a phenomenon ob-served as early as 1929(2)but which resonated in physical sci
ences only after Duncan Watts and Stephen Strogatz extended its reach beyond so-ciology (5).Yet,the undeniable success of the random hypothesis did pose a fundamental ques-tion:Are real networks truly random?That is,could systems such as the cell or a society func-tion seamlessly if their nodes,molecules,or people were wired randomly together?This ques-tion motivated our work as well,leading 10years ago to the discovery of the scale-free property (6,7).
Our first clue that real networks may show manifestly nonrandom features also came 10years ago from a map of the World Wide Web (WWW)(8),finding that the probability that a Web page has exactly k links (in other words,degree k )follows a power law distribution
P (k )~k小姨的梦
-g
(1)
a stunning departure from the Poisson distribu-tion predicted by random network theory (1).Yet,it was not until we realized that Eq.1character-izes the network of actors linked by movies and scientific papers linked by citations (9)that we
suspected that the scale-free property (6)might not be unique to the WWW.The main purpose of the 1999Science paper was to report this unexpected similarity between networks of quite different nature and to show that two mechanisms,growth and preferential attachment,are the underlying causes (Fig.1).
When we concluded in 1999that we “expect that the scale invariant state […]is a generic
property of many complex networks ”(7),it was more of a prediction than a fact,because nature could have chosen as many different architec-tures as there are networks.Yet,probably the most surprising discovery of modern network theory is the universality of the network topology:Many real networks,from the cell to the Internet,independent of their age,function,and scope,converge to similar architectures.It is this uni-versality that allowed researchers from different disciplines to embrace network theory as a com-mon paradigm.
中国刀剪剑博物馆
Today,the scale-free nature of networks of key scientific interest,from protein interactions to social networks and from the network of inter-linked documents that make up the WWW to the interconnected hardware behind the Internet,has been established beyond doubt.The evidence comes not only from better maps and data sets but also from the agreement between empirical data
and analytical models that predict the network structure (10,11).Yet,the early euphoria was not without negative side effects,prompting some re-searchers to label many systems scale-free,even when the evidence was scarce at best.However,the net result was to force us to better understand the factors that shape network structure.For ex-
Pushing Networks to the Limit
Center for Complex Network Research,Department of Physics,Biology,and Computer Science,Northeastern University,Boston,MA 02115,USA.Department of Medicine,Harvard Medical School and Center for Cancer Systems Biology,Dana Farber Cancer Institute,Boston,MA 02115,USA.E-mail:alb@neu.edu
Fig.1.The birth of a scale-free network.(Top and Middle )The simplest process that can produce a scale-free topology was introduced a decade ago in (6),and it is illustrated in the top two rows.Starting from three connected nodes (top left),in each image a new node (shown as an empty circle)is added to the network.When deciding where to link,new nodes prefer to attach to the more connected nodes,a process known as preferential attachment.Thanks to growth and preferential attachment,a rich-gets-richer process is observed,which means that the highly connected nodes acq
uire more links than those that are less connected,leading to the natural emergence of a few highly connected hubs.The node size,which was chosen to be proportional to the node ’s degree,illustrates the natural emergence of hubs as the largest nodes.The degree distribution of the resulting network follows the power law (Eq.1)with exponent g =3.See also movies S1to S3.(Bottom )Illustration of the growth process in the co-authorship network of physicists.Each node corresponds to an individual author,and two nodes are connected if they co-authored a paper together.The four images show the network ’s growth at 1-month time intervals,indicating how the network expands in time,leading to the emergence of a clear hub.Once again,the node size was chosen to be proportional to the node ’s degree.[Credit:D.Wang and G.Palla]
24JULY 2009
VOL 325
SCIENCE
412 o n  J u l y  24, 2009
w w w .s c i e n c e m a g .o r g D o w n l o a d e d  f r o m
ample,although the randomly bonded atoms in amorphous materials form a fascinating network,we now know that it does not display either the small-world (12)or the scale-free property,thanks to the chemical constraints the bonds must obey (13).Lastly,the topologies of several networks of considerable interest,like the neural-level map of a mammalian brain,remain to be elucidated,rep-resenting an area where we need both data and generative models (14).
A legacy of the scale-free property is the re-alization that the structure and
the evolution of networks are inseparable (6).Indeed,traditional network models aimed to connect a fixed number of nodes with cleverly placed links.The scale-free property forced us to acknowledge that networks constantly change because of the arrival of nodes and links (Fig.1).In other words,to explain a system ’s topology we first need to describe how it came into being.
The impact of network theory could have been limited if not for a series of findings that under-lined th
e perils of ignoring network topology.Take,for example,the discovery of Romualdo Pastor-Satorras and Alessandro V espignani that on a scale-free network the epidemic threshold converges to zero (15).It has long been known that only viruses whose spreading rate exceeds a critical threshold can survive in the population.Whereas the spread-ing rate captures the transmission dynamics,the threshold is determined by the topology of the network on which the virus spreads.Therefore,the vanishing threshold means that in scale-free networks even weakly virulent viruses can spread unopposed,a finding that affects all spreading processes,from AIDS to computer viruses.Simi-larly,the finding of Shlomo Havlin and collab-orators (16)that in scale-free networks the overall network connectivity does not vanish under random node removal explained the exceptional robustness of real networks to random node failures (17).As a proof of the coherency of the emerging theory,both of these discoveries (15,16)were reduced to the same mathematical property,the diverging second moment of the degree distribution (Eq.1),a unique feature of scale-free networks (6).Lately these features are of great interest,given the increasing concern about the vulnerability of real networks (such as power grids and the Internet)to attack and the realiza-tion that targeting hubs can be massively dis-ruptive (17,18).
It is clear that no networks seen in nature or technology are completely random —that is,mech-anis
ms beyond randomness shape their evolution.The universality of various topological character-istics,from degree distributions (6)to degree correlations (19–21),motifs (22),and commu-nities (23–25),is used as a springboard to study diverse phenomena and to make predictions.With that,network theory has fundamentally reshaped our understanding of complexity.Indeed,al-though we continue to lack a universally agreed-on definition of complexity,the role of networks in this area is obvious:All systems perceived to be complex,from the cell to the Internet and from social to economic systems,consist of an extra-ordinarily large number of components that inter-act via intricate networks.To be sure,we were aware of these networks before.Y et,only recently have we acquired the data and tools to probe their topology,helping us realize that the underlying connectivity has such a strong impact on a system ’s behavior that no approach to complex systems can succeed unless it exploits the network topology.
jams or how the cell reacts to changes in its en-vironment.To make progress in this direction,we need to tackle the next frontier,which is to under-stand the dynamics of the processes that take place on networks.The problem is that we have almost as many dynamical phenomena as there are com-plex systems.For example,biologists study re-action kinetics on metabolic networks;computer scientists monitor the flow of information on com-puter networks;and epidemiologists,sociologists,an
d economists explore the spread of viruses and ideas on social networks.Is there a chance that,despite their diversity,these dynamical processes share some common characteristics?I suspect that such commonalities do exist;we just have not yet found the framework to unveil their univer-sality.If we do,combined with the universality of the network topology,we may soon have some-thing that could form the foundation of a theory of complexity.
Can we keep the momentum and achieve this in the next decade or so?Perhaps —in my view the bottlenecks are mainly data driven.Indeed,the sudden emergence of large and reliable network maps drove the development of network theory during the past decade.If data of similar detail capturing the dynamics of processes taking place on networks were to emerge in the coming years,our imagination will be the only limitation to progress.If I dare to make a prediction for the next decade,it is this:Thanks to the proliferation of the many electronic devices that we use on a daily basis,from cell phones to Global Position-ing Systems and the Internet,that capture every-thing from our communications to our whereabouts (26,27),the complex system that we are most likely to tackle first in a truly quantitative fashion may not be the cell or the Internet but rather society itself.
Today the understanding of networks is a com-mon goal of an unprecedented array of traditional disciplines:Cell biologists use networks to make sense of signal transduction cascades and metab-ol
ism,to name a few applications in this area;computer scientists are mapping the Internet and
the WWW;epidemiologists follow transmission networks through which viruses spread;and brain researchers are after the connectome,a neural-level connectivity map of the brain.Although many fads have come and gone in complexity,one thing is increasingly clear:Interconnectivity is so fundamental to the behav-ior of complex systems that networks are here to stay.
References and Notes
1.P.Erd ős,A.Rényi,Publ.Math.(Debrecen)6,290(1959).
2.F.Karinthy,in The Structure and Dynamics of Networks ,M.Newman,A.-L.Barabasi,D.Watts,Eds.(Princeton Univ.Press,Princeton,NJ,2006).
3.S.Milgram,Psychol.Today 2,60(1967).
4.I.Pool,M.Kochen,Soc.Networks 1,1(1978).
5.D.J.Watts,S.H.Strogatz,Nature 393,440(1998).
6.A.-L.Barabási,R.Albert,Science 286,509(1999).
7.In a random network,the average node sets the scale of the network,which means that most nodes have about the same number of links as the average node.For networks that follow Eq.1,for g <3the second moment of the distribution diverges,which means that the average is not characteristic because the error bars characterizing our uncertainty about its value are infinite.These networks lack a characteristic scale;hence,they are called scale-free.Formally,networks whose degree distribution follows Eq.1are called scale-free networks.
8.R.Albert,H.Jeong,A.-L.Barabási,Nature 401,130(1999).长征之路
9.S.Redner,Eur.Phys.J.B 4,131(1998).
10.G.Caldarelli,Scale-Free Networks (Oxford Univ.Press,
Oxford,2007).
11.S.N.Dorogovtsev,J.F.F.Mendes,Evolution of Networks:
From Biological Networks to the Internet and WWW (Oxford Univ.Press,Oxford,2003).
12.The small-world property refers to the fact that in many
networks the average node to node distance is rather small,of the order of log N ,where N is the number of nodes in the network.
13.L.A.N.Amaral,A.Scala,M.Barthelemy,H.E.Stanley,
Proc.Natl.Acad.Sci.U.S.A.97,11149(2000).
14.E.T.Bullmore,O.Sporns,Nat.Rev.Neurosci.10,186
(2009).
15.R.Pastor-Satorras,A.Vespignani,Phys.Rev.Lett.86,
3200(2001).
16.R.Cohen,K.Reez,D.Ben-Avraham,S.Havlin,Phys.Rev.
Lett.85,4626(2000).
17.R.Albert,H.Jeong,A.-L.Barabási,Nature 406,378
(2000).
18.A.E.Motter,Phys.Rev.Lett.93,098701(2004).19.M.E.J.Newman,Phys.Rev.Lett.89,208701
(2002).
20.R.Pastor-Satorras,A.Vázquez,A.Vespignani,Phys.Rev.
Lett.87,258701(2001).
21.S.Maslov,K.Sneppen,Science 296,910(2002).22.R.Milo et al .,Science 298,824(2002).
23.M.E.J.Newman,Phys.Today 61,33(2008).科学领域教案中班
24.G.Palla,I.Derényi,I.Farkas,T.Vicsek,Nature 435,814
(2005).
25.J.Reichardt,S.Bornholdt,Phys.Rev.E 74,016110
(2006).
26.A.Vespignani,Science 325,425(2009).
27.M.C.González,C.A.Hidalgo,A.-L.Barabási,Nature
453,779(2008).
Supporting Online Material
/cgi/content/full/325/5939/412/DC1Movies S1to S310.1126/science.1173299外国美术史
SCIENCE
VOL 325
24JULY 2009413
车辆未年检上路怎么处罚规定
SPECIAL SECTION
o n  J u l y  24, 2009
w w w .s c i e n c e m a g .o r g D o w n l o a d e d  f r o m