Persistence of hubs in growing random networks

We consider models of evolving networks (G(n) : n >= 0) modulated by two parameters: an attachment function f : N-0 -> R+ and a (possibly random) attachment sequence (mi : i >= 1). Starting with a single vertex, at each discrete step i >= 1 a new vertex vi enters the system with m(i) >= 1 edges which it sequentially connects to a preexisting vertex v is an element of G(i-1) with probability proportional to f (degree(v)). We consider the problem of emergence of persistent hubs: existence of a finite (a.s.) time n* such that for all n >= n* the identity of the maximal degree vertex (or in general the K largest degree vertices for K >= 1) does not change. We obtain general conditions on f and (m(i) : i >= 1) under which a persistent hub emerges, and also those under which a persistent hub fails to emerge. In the case of lack of persistence, for the specific case of trees (m(i) (math) 1 for all i), we derive asymptotics for the maximal degree and the index of the maximal deg ree vertex (time at which the vertex with current maximal degree entered the system) to understand the movement of the maximal degree vertex as the network evolves. A key role in the analysis is played by an inverse rate weighted martingale constructed from a continuous time embedding of the discrete time model. Asymptotics for this martingale, including concentration inequalities and moderate deviations form the technical foundations for the main results.

Automated summary

The study focuses on evolving network models modulated by two parameters and the emergence of persistent hubs. General conditions for the emergence or lack thereof of persistent hubs were obtained, with specific asymptotic analysis for the case of trees in the absence of persistence. The analysis relies on an inverse rate weighted martingale and provides technical foundations for the main results, including concentration inequalities and moderate deviations.