We investigate node degrees in a network grown from a seed by hooking self-similar components under two models of randomness: a uniform model and a model based on preferential attachment. We study two degree profiles: a local profile tracking the evolution of the degree of a particular node over time, and a global profile concerned about counts of the number of nodes of a particular degree.
For the local profile, under uniform growth, we have the exact mean, variance and probability distribution in terms of standard combinatorial numbers like generalized harmonic numbers and Stirling numbers of the first kind. Asymptotically, we observe phases: The early nodes have an asymptotically normal distribution, intermediate nodes have a Poisson distribution and the late nodes have a degenerate distribution. In contrast, under preferential attachment, the moments of the degree of a node contain Stirling numbers of the second kind and (under appropriate scaling) has a gamma-type limit law.
As for the global profile, we use Polya urns to derive strong laws. Four regimes arise according to the structure of the seed. Within these regimes, we identify a few degenerate cases. Barring these degenerate cases, we uncover an asymptotically normal joint multivarite distribution for nodes of very small degrees.
AMS subject classifications:
Primary: 05082, Complex networks
90B15; Stochastic network models
Secondary: 60C05, Combinatorial probability
60F05, Central limit and other weak theorems
Keywords: Network, random graph, degree profile, Polya urn, limit law, preferential attachment, phase transition, Stirling number.
more upcoming events
No upcoming events