Preferential Attachment Random Graphs

Abstract: Consider a random graph evolving in discrete time as follows. At time zero there are two vertices connected to each other. At time one a third vertex appears and connects to one of the first two with equal probability. at the nth step the new vertex connects to one of the previous vertices with probability proportional to a weight function of the degree of that vertex, the degree being the number of connections coming from that vertex. We study the growth of the degree vector and the degree distribution as n gets large.Our method consists of embedding this discrete time sequence in a continuous time set up and use results from pure birth processes.