Preferential attachment with choice1. Issue 4 (28th November 2015) - Haslegrave, John; Jordan, Jonathan
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 asymptotically follows a power law with logarithmic correction when r = 2 and shows condensation‐like behaviour when r > 2 . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 751–766, 2016