Preferential attachment with choice

John Haslegrave and Jonathan Jordan
Random Structures and Algorithms, Vol. 48, pp751-766 (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.

Link to paper on ArXiv

Link to paper on journal website

Back to my research page.
Last updated 2 July 2018.