De-Preferential Attachment Random Graphs

In this talk we will introduce a new model of a growing sequence of random graphs where a new vertex is less likely to join to an existing vertex with high degree and more likely to join to a vertex with low degree. In contrast to the well studied model of preferential attachment random graphs where higher degree vertices are preferred, we will call our model de-preferential attachment random graph model. We will consider two types of de-preferential attachment models, namely, inverse de-preferential, where the attachment probabilities are inversely proportional to the degree and linear de-preferential, where the attachment probabilities are proportional to c-degree, where c>0 is a constant. We will give asymptotic degree distribution for both the models and show that the limiting degree distribution has very thin tail. We will also show that for a fixed vertex v, the degree grows as logn‾‾‾‾‾√ for the inverse de-preferential case and as logn for the linear case. Some of the results will also be generalized when each new vertex joins to m>1 existing vertices.
This is a joint work with Subhabrata Sen, Stanford University.