Persistence of hubs in growing random networks

• 成果类型: Article
• 署名作者: Banerjee, Sayan; Bhamidi, Shankar
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-021-01066-0
• 发表日期: 2021
• 页码: 891-953
• 关键词: maximum degree; trees; CONVERGENCE; centrality

摘要

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.