Connectivity of Growing Random Networks

Connectivity of Growing Random Networks

18 Sep 2000 | P. L. Krapivsky, S. Redner, and F. Leyvraz
This paper presents a solution for the time- and age-dependent connectivity distribution of a growing random network. The network is built by adding sites that link to earlier sites with a probability $ A_k $, which depends on the number of pre-existing links $ k $ to that site. For homogeneous connection kernels $ A_k \sim k^\gamma $, different behaviors arise for $ \gamma < 1 $, $ \gamma > 1 $, and $ \gamma = 1 $. For $ \gamma < 1 $, the number of sites with $ k $ links, $ N_k $, varies as a stretched exponential. For $ \gamma > 1 $, a single site connects to nearly all other sites. In the borderline case $ A_k \sim k $, the power law $ N_k \sim k^{-\nu} $ is found, where the exponent $ \nu $ can be tuned to any value in the range $ 2 < \nu < \infty $. The paper discusses the GRN model, which is defined by adding a new site and a directed link to one of the earlier sites. The structure of the graph is determined by the connection kernel $ A_k $, which is the probability that a newly-introduced site links to an existing site with $ k $ links. The connectivity distribution $ N_k(t) $ is solved for the case of homogeneous connection kernels $ A_k = k^\gamma $, with $ \gamma \geq 0 $. The connectivity distribution crucially depends on whether $ \gamma $ is smaller than, larger than, or equal to unity. For $ \gamma < 1 $, the connectivity distribution decreases as a stretched exponential in $ k $. For $ \gamma > 1 $, a single "gel" site connects to nearly every other site. For $ \gamma = 1 $, a power law distribution $ N_k \sim k^{-\nu} $ arises, with $ \nu $ tunable to any value in the range $ 2 < \nu < \infty $. The paper also discusses the age-dependent structure of the growing random network. Older sites are more highly connected, and the age distribution of sites with $ k $ links is analyzed. The results show that the most popular site has a connectivity $ k_{\max} $ that depends on $ \gamma $. The paper concludes that the GRN model with an asymptotically linear connection kernel exhibits a power-law distribution $ N_k \sim k^{-\nu} $, with $ \nu $ tunable to any value in the range $ 2 < \nu < \infty $. This accords with the connectivity distributions observed in various contemporary examples of growing networks.This paper presents a solution for the time- and age-dependent connectivity distribution of a growing random network. The network is built by adding sites that link to earlier sites with a probability $ A_k $, which depends on the number of pre-existing links $ k $ to that site. For homogeneous connection kernels $ A_k \sim k^\gamma $, different behaviors arise for $ \gamma < 1 $, $ \gamma > 1 $, and $ \gamma = 1 $. For $ \gamma < 1 $, the number of sites with $ k $ links, $ N_k $, varies as a stretched exponential. For $ \gamma > 1 $, a single site connects to nearly all other sites. In the borderline case $ A_k \sim k $, the power law $ N_k \sim k^{-\nu} $ is found, where the exponent $ \nu $ can be tuned to any value in the range $ 2 < \nu < \infty $. The paper discusses the GRN model, which is defined by adding a new site and a directed link to one of the earlier sites. The structure of the graph is determined by the connection kernel $ A_k $, which is the probability that a newly-introduced site links to an existing site with $ k $ links. The connectivity distribution $ N_k(t) $ is solved for the case of homogeneous connection kernels $ A_k = k^\gamma $, with $ \gamma \geq 0 $. The connectivity distribution crucially depends on whether $ \gamma $ is smaller than, larger than, or equal to unity. For $ \gamma < 1 $, the connectivity distribution decreases as a stretched exponential in $ k $. For $ \gamma > 1 $, a single "gel" site connects to nearly every other site. For $ \gamma = 1 $, a power law distribution $ N_k \sim k^{-\nu} $ arises, with $ \nu $ tunable to any value in the range $ 2 < \nu < \infty $. The paper also discusses the age-dependent structure of the growing random network. Older sites are more highly connected, and the age distribution of sites with $ k $ links is analyzed. The results show that the most popular site has a connectivity $ k_{\max} $ that depends on $ \gamma $. The paper concludes that the GRN model with an asymptotically linear connection kernel exhibits a power-law distribution $ N_k \sim k^{-\nu} $, with $ \nu $ tunable to any value in the range $ 2 < \nu < \infty $. This accords with the connectivity distributions observed in various contemporary examples of growing networks.
Reach us at info@study.space
[slides and audio] Connectivity of growing random networks.