PaperlayerView exact revision on arXiv

Source-linked AI summary

Emergence of scaling in random networks

Albert-Laszlo Barabasi, Reka Albert

arXiv:cond-mat/9910332v1cond-mat.dis-nnadap-orgcond-mat.stat-mechnlin.AO

TL;DR

Large networks across biology, neuroscience, social systems, and the web exhibit complex topology that is difficult to describe. The paper reports self-organization in such networks and models it using continuous growth with preferential attachment, reproducing scale-free connectivity patterns. The model’s scope is limited because it does not capture all aspects of the studied networks.

Abstract

from arXiv · show

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 is found to be a consequence of the two generic mechanisms that networks expand continuously by the addition of new vertices, and new vertices attach preferentially to already well connected sites. A model based on these two ingredients reproduces the observed stationary scale-free distributions, indicating 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 describe systems composed of non-identical

Complex networks arise across biology, neuroscience, social science, and the web, but their large size and nonlocal interactions make them difficult to describe. These systems are represented as vertices connected by edges that encode interactions.

The inability of contemporary science to describe systems composed of non-identical

Traditionally, networks of complex topology have been described using the random graph

This section examines how continuous network growth and preferential attachment produce stationary scale-free connectivity distributions. It presents the resulting power-law behavior and discusses conditions and extensions that limit or modify it.

  • The cited networks show power-law tails for large k, with exponents between 2.1 and 4; actors have γactor = 2.3 ± 0.1 and webpages γwww = 2.1 ± 0.1.Source: Traditionally, networks of complex… · pp. 3–4
  • ER and WS models suppress highly connected vertices through exponentially decaying or peaked connectivity distributions, unlike the observed power-law tails.These models also assume a fixed number of vertices and uniform random connectivity, whereas real networks continuously add vertices and favor already well-connected ones.Source: Traditionally, networks of complex… · p. 4
  • A growing preferential-attachment model produces a scale-invariant network with γmodel = 2.9±0.1, matching the power-law mechanism proposed for real networks.Starting from m0 vertices, each timestep adds one vertex with m edges linked to existing vertices with probability depending on their connectivity.Source: Traditionally, networks of complex… · p. 5
  • The model’s P(k) is independent of time and system size, indicating that continuous growth self-organizes the network into a scale-free state.This time independence is required because real networks are observed at different sizes and developmental stages.Source: Traditionally, networks of complex… · p. 5
  • The paper tests the necessity of preferential attachment by retaining growth while assigning new connections uniformly across existing vertices.This variant is specified to yield P(k) ∼exp(−βk), rather than the scale-free distribution of the full model.Source: Traditionally, networks of complex… · pp. 5–6

Model ingredients

  • Both growth and preferential attachment are required to produce the stationary power-law distribution observed in real networks.Without preferential attachment, the scale-free feature disappears; without growth, the distribution is transient and the network eventually becomes fully connected.Source: Traditionally, networks of complex… · p. 6

Preferential attachment mechanism

  • Preferential attachment amplifies initial connectivity differences, causing older vertices to become increasingly connected through a “rich-gets-richer” process.The connectivity follows ∂k_i/∂t = k_i/2t and k_i(t) = m(t/t_i)^0.5, a scaling relation testable with time-resolved network data.Source: Traditionally, networks of complex… · p. 6

Stationary distribution

  • The model analytically gives γ = 3, independent of m, reproducing the observed scale-free distribution.The stationary solution follows from the connectivity growth law and the probability distribution of vertex arrival times.Source: Traditionally, networks of complex… · p. 7

Model conditions

  • Scaling occurs only for linear preferential attachment Π(k) ∼ k, whereas observed network exponents range from 2.1 to 4.For nonlinear attachment Π(k) ∼ k^α, simulations indicate scaling only when α = 1.Source: Traditionally, networks of complex… · p. 7

Scope and limitations

  • Although system-specific processes can modify γ, the model provides the first successful mechanism accounting for the scale-invariant nature of real networks.The framework does not include all network features, such as adding or removing connections between established vertices; directed links provide one extension with γ(p) = 3 − p.Source: Traditionally, networks of complex… · p. 7

Growth and preferential attachment are mechanisms common to a number of complex

Growth and preferential attachment are presented as mechanisms that can produce scale-free structure across diverse complex networks. The resulting scale-invariant state may extend beyond the specific systems with currently detailed topological data.

Loading cond-mat/9910332v1…