Accelerating, hyper-accelerating, and decelerating probabilistic networks

Abstract

Many growing networks possess accelerating statistics where the number of links added with each new node is an increasing function of network size so the total number of links increases faster than linearly with network size. In particular, biological networks can display a quadratic growth in regulator number with genome size even while remaining sparsely connected. These features are mutually incompatible in standard treatments of network theory which typically require that every new network node possesses at least one connection. To model sparsely connected networks, we generalize existing approaches and add each new node with a probabilistic number of links to generate either accelerating, hyper-accelerating, or even decelerating network statistics in different regimes. Under preferential attachment for example, slowly accelerating networks display stationary scale-free statistics relatively independent of network size while more rapidly accelerating networks display a transition from scale-free to exponential statistics with network growth. Such transitions explain, for instance, the evolutionary record of single-celled organisms which display strict size and complexity limits.

13 pages, 9 figures

References in corpus (7)

• The structure and function of complex networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Preferential attachment in the protein network evolution
• Accelerated growth in outgoing links in evolving networks: deterministic vs. stochastic picture
• Directed Accelerated Growth: Application in Citation Network
• Preferential attachment with information filtering - node degree probability distribution properties
• Failed "nonaccelerating" models of prokaryote gene regulatory networks

Cited by in corpus (7)

• Effects of accelerating growth on the evolution of weighted complex networks
• Accelerating networks
• Preferential attachment during the evolution of a potential energy landscape
• Master-equation analysis of accelerating networks
• Time-invariant degree growth in preferential attachment network models
• Sustainable growth in complex networks
• A self-consistent approach to measure preferential attachment in networks and its application to an inherent structure network