2025/08/25 by Bandyopadhyay, Antar, Sen, Subhabrata
#FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2508.18144
In this work we consider a growing random graph sequence 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 preferential attachment random graphs \citeBarAlb99, we call such a sequence a de-preferential attachment random graph model. We consider two types of 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. For the case when each new vertex comes with exactly one half-edge we show that the degree of a fixed vertex is asymptotically of the order √(log n) for the inverse de-preferential case and of the order log n for the linear case. These show that compared to preferential attachment, the degree of a fixed vertex grows to infinity at a much slower rate for these models. We also show that in both cases limiting degree distributions have exponential tails. In fact we show that for the inverse de-preferential model the tail of the limiting degree distribution is faster than exponential while that for the linear de-preferential model is exactly the Geometric((1)/(2)) distribution. For the case when each new vertex comes with m > 1 half-edges, we show that similar asymptotic results hold for fixed vertex degree in both inverse and linear de-preferential models. Our proofs make use of the martingale approach as well as embedding to certain continuous time age dependent branching processes.