Preferential attachment with choice (2016)

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 sth 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.

The picture below shows a simulation to 200 vertices of the case where r=2 and s=1.