Preferential attachment with choice1. Issue 4 (28th November 2015)

• Record Type: Journal Article
• Authors: Haslegrave, John; Jordan, Jonathan
• Is Part Of: Random structures & algorithms. Volume 48:Issue 4(2016)
• Page Start: 751
• Page End: 766
• Publication Date: 2015-11-28
• Subjects: random graphs -- preferential attachment -- choice; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20616
• Languages: English
• ISSNs: 1042-9832

Abstract

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