Network Growth with Arbitrary Initial Conditions: Analytical Results for Uniform and Preferential Attachment

Abstract

This paper provides time-dependent expressions for the expected degree distribution of a given network that is subject to growth, as a function of time. We consider both uniform attachment, where incoming nodes form links to existing nodes selected uniformly at random, and preferential attachment, when probabilities are assigned proportional to the degrees of the existing nodes. We consider the cases of single and multiple links being formed by each newly-introduced node. The initial conditions are arbitrary, that is, the solution depends on the degree distribution of the initial graph which is the substrate of the growth. Previous work in the literature focuses on the asymptotic state, that is, when the number of nodes added to the initial graph tends to infinity, rendering the effect of the initial graph negligible. Our contribution provides a solution for the expected degree distribution as a function of time, for arbitrary initial condition. Previous results match our results in the asymptotic limit.

References in corpus (5)

• The Dynamics of Viral Marketing
• Citation Statistics from 110 Years of Physical Review
• Accurately modeling the Internet topology
• An Opinion Dynamics Model for the Diffusion of Innovations
• Network Marketing on a Small-World Network

Cited by in corpus (7)

• Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs
• Growing Multiplex Networks with Arbitrary Number of Layers
• Simon's fundamental rich-get-richer model entails a dominant first-mover advantage
• The effect of the initial network configuration on preferential attachment
• Analytic solutions for links and triangles distributions in finite Barabási-Albert networks
• Temporal Dynamics of Connectivity and Epidemic Properties of Growing Networks
• Inter-layer Degree Correlations in Heterogeneously Growing Multiplex Networks