1212.0435 (Babak Fotouhi et al.)

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

Babak Fotouhi, Michael G. Rabbat

This paper provides exact 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.

View original: http://arxiv.org/abs/1212.0435