Organization of growing random networks.

By Paul L. Krapivsky, Sidney Redner. Physical review. E, Statistical, nonlinear, and soft matter physics, 2000

776 citations recorded by the source corpus.

The organizational development of growing random networks is investigated. These growing networks are built by adding nodes successively, and linking each to an earlier node of degree k with an attachment probability A(k). When A(k) grows more slowly than linearly with k, the number of nodes with k links, N(k)(t), decays faster than a power law in k, while for A(k) growing faster than linearly in k, a single node emerges which connects to nearly all other nodes. When A(k) is asymptotically linear, N(k)(t) approximately tk(-nu), with nu dependent on details of the attachment probability, but in the range 2<nu<infinity. The combined age and degree distribution of nodes shows that old nodes typically have a large degree. There is also a significant correlation in the degrees of neighboring nodes, so that nodes of similar degree are more likely to be connected. The size distributions of the in and out components of the network with respect to a given node--namely, its "descendants" and "ancestors"-are also determined. The in component exhibits a robust s(-2) power-law tail, where s is the component size. The out component has a typical size of order ln t, and it provides basic insights into the genealogy of the network.

Subfields: Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/be12e4e06ff028cc9a6ed4ccbfc35ed9153c98c7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

An almost-bijective proof of an asymptotic property of partitions (2007, background): “General weight functions are considered in the model of Krapivsky and Redner [9].”
A Brief History of Generative Models for Power Law and Lognormal Distributions (2004, background): “A simple if slightly non-rigorous argument for the above model goes as follows [21, 35].”
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. (2000, background): “The basic statistics of the previous section are certainly of importance, particularly for the construction of network models (Watts and Strogatz, 1998; Albert et al., 1999; Kleinberg, 2000; Newman et al., 2001; Krapivsky and Redner, 2001), but there is much more that we can do with our collaboratio”
The “New” Science of Networks (2004, background): “Rather than assuming preferential attachment as a fundamental feature of network growth, Krapivsky & Redner (2001) showed that it can be derived from more basic growth assumptions: ( a ) that new arrivals select a member probability q they are redirected by their initial choice to one of its…”
Statistical mechanics of complex networks (2001, methodology): “Although inspired by a different mechanism, the growing network with the redirection model of Krapivsky and Redner (2001) is mathematically equivalent with the model of Kumar et al. (2000a, 2000b) discussed above.”
Fringe trees, Crump-Mode-Jagers branching processes and $m$-ary search trees (2016, background): “for some p > 1 is studied by Krapivsky, Redner and Leyvraz [88], Krapivsky and Redner [87] and (rigorously and in detail) by Oliveira and Spencer [108], who show that if p > 2 (but not if 1 < p 6 2), the random tree process Tn, n > 1, is even more strongly degenerate: a.”
Evolution of networks (2001, methodology): “7) in the framework of this approach can be found in reference [95].”
The Structure and Function of Complex Networks (2003, methodology): “For useful feedback on early versions of this article, the author would particularly like to thank Lada Adamic, Michelle Girvan, Petter Holme, Randy LeVeque, Sidney Redner, Ricard Solé, Steve Strogatz, Alexei Vázquez, and an anonymous referee.”
Generalizations of Polya's urn Problem (2003, methodology): “The innite Polya process is motivated by a variation of a web tree-graph model proposed by Drinea et al. [6] and by Kaprivsky and Redner [ 9 ].”