Preferential attachment with choice

Abstract

We consider the degree distributions of preferential attachment random graph models with choice similar to those considered in recent work by Malyshkin and Paquette and Krapivsky and Redner. In these models a new vertex chooses $r$ vertices according to a preferential rule and connects to the vertex in the selection with the $s$th highest degree. For meek choice, where $s>1$, we show that both double exponential decay of the degree distribution and condensation-like behaviour are possible, and provide a criterion to distinguish between them. For greedy choice, where $s=1$, we confirm that the degree distribution asympotically follows a power law with logarithmic correction when $r=2$ and shows condensation-like behaviour when $r>2$.

17 pages, 1 figure. Accepted for publication in Random Structures and Algorithms

References in corpus (4)

• The power of choice in network growth
• Choice-Driven Phase Transition in Complex Networks
• The power of 2 choices over preferential attachment
• The power of choice combined with preferential attachment

Cited by in corpus (7)

• The Fluid Mechanics of Liquid Democracy
• Random Recursive Hypergraphs
• Preferential attachment with location-based choice: Degree distribution in the noncondensation phase
• Condensation in preferential attachment models with location-based choice
• On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
• The Power of Two Choices for Random Walks
• Preferential attachment with fitness dependent choice