Emergence of Scaling in Random Networks

Abstract

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 mechanisms: (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.

Keywords

Vertex (graph theory)Complex networkScalingScale-free networkComputer scienceTopology (electrical circuits)Preferential attachmentTheoretical computer scienceRandom graphStatistical physicsMathematicsCombinatoricsPhysicsGraphWorld Wide Web

Affiliated Institutions

University of Notre Dame US

Related Publications

Statistical mechanics of complex networks

Réka Albert , Albert‐László Barabási

Complex networks describe a wide range of systems in nature and society, much\nquoted examples including the cell, a network of chemicals linked by chemical\nreactions, or the I...

2002 Reviews of Modern Physics 20121 citations

Random graphs with arbitrary degree distributions and their applications

M. E. J. Newman , Steven H. Strogatz , Duncan J. Watts

Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Po...

2001 Physical review. E, Statistical physi... 3631 citations

Network Representation Learning: A Survey

Daokun Zhang , Jie Yin , Xingquan Zhu +1 more

With the widespread use of information technologies, information networks are becoming increasingly popular to capture complex relationships across various disciplines, such as ...

2018 IEEE Transactions on Big Data 685 citations

Global snapshot of a protein interaction network—a percolation based approach

Chen-Shan Chin , Manoj P. Samanta

Abstract Motivation: Biologically significant information can be revealed by modeling large-scale protein interaction data using graph theory based network analysis techniques. ...

2003 Bioinformatics 46 citations

Are randomly grown graphs really random?

Duncan S. Callaway , John E. Hopcroft , Jon Kleinberg +2 more

We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, two vertices are chosen uniformly at random and joined b...

2001 Physical review. E, Statistical physi... 443 citations

Publication Info

Year: 1999
Type: article
Volume: 286
Issue: 5439
Pages: 509-512
Citations: 35356
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Emergence of Scaling in Random Networks

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

35356

OpenAlex

Cite This

APA Style

                            
                                    Albert‐László Barabási, 
                                
                                    Réka Albert
                                
                            (1999). 
                            Emergence of Scaling in Random Networks. 
                            Science
                            , 286
                            (5439)
                            , 509-512.
                            https://doi.org/10.1126/science.286.5439.509

Identifiers

DOI: 10.1126/science.286.5439.509