TY - JOUR

T1 - Robust analysis of preferential attachment models with fitness

AU - Dereich, Steffen

AU - Ortgiese, Marcel

PY - 2014/5

Y1 - 2014/5

N2 - The preferential attachment network with fitness is a dynamic random graph model. New vertices are introduced consecutively and a new vertex is attached to an old vertex with probability proportional to the degree of the old one multiplied by a random fitness. We concentrate on the typical behaviour of the graph by calculating the fitness distribution of a vertex chosen proportional to its degree. For a particular variant of the model, this analysis was first carried out by Borgs, Chayes, Daskalakis and Roch. However, we present a new method, which is robust in the sense that it does not depend on the exact specification of the attachment law. In particular, we show that a peculiar phenomenon, referred to as Bose–Einstein condensation, can be observed in a wide variety of models. Finally, we also compute the joint degree and fitness distribution of a uniformly chosen vertex.

AB - The preferential attachment network with fitness is a dynamic random graph model. New vertices are introduced consecutively and a new vertex is attached to an old vertex with probability proportional to the degree of the old one multiplied by a random fitness. We concentrate on the typical behaviour of the graph by calculating the fitness distribution of a vertex chosen proportional to its degree. For a particular variant of the model, this analysis was first carried out by Borgs, Chayes, Daskalakis and Roch. However, we present a new method, which is robust in the sense that it does not depend on the exact specification of the attachment law. In particular, we show that a peculiar phenomenon, referred to as Bose–Einstein condensation, can be observed in a wide variety of models. Finally, we also compute the joint degree and fitness distribution of a uniformly chosen vertex.

UR - https://doi.org/10.1017/S0963548314000157

U2 - 10.1017/S0963548314000157

DO - 10.1017/S0963548314000157

M3 - Article

VL - 23

SP - 386

EP - 411

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 3

ER -