Combinatorics-Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment

Speaker: Hosam Mahmoud, GW Department of Statistics
Date and time: Tuesday, April 10, 1-2pm
Place: Rome 771
Title: Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment

Abstract: 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.