Preferential Attachment Random Graphs with General Weight Function

(Abstract)

Consider a network of sites growing over time such that at step n a newcomer chooses a vertex from the existing vertices with probability proportional to a function of the degree of that vertex, i.e., the number of other vertices that this vertex is connected to. This is called a preferential attachment random graph. The objects of interest are the growth rates for the growth of the degree for each vertex with n and the behavior of the empirical distribution of the degrees. In this talk we will consider three cases: the weight function w(.) is superlinear, linear, and sublinear. Using recently obtained limit theorems for the growth rates of a pure birth continuous time Markov chains and an embedding of the discrete time graph sequence in a sequence of continuous time pure birth Markov chains, we establish a number of results for all the three cases. We show that the much discussed power law growth of the degrees and the power law decay of the limiting degree distribution hold only in the linear case, i.e., when w(.) is linear.