High degree vertices in the Power of Choice model combined with Preferential Attachment

preprint2016arXivOpen access

Abstract

We find assimpotics for the first kk highest degrees of the degree distribution in an evolving tree model combining the local choice and the preferential attachment. In the considered model, the random graph is constructd in the following way. At each step, a new vertex is introduced. Then, we connect it with one (the vertex with the largest degree is chosen) of dd (d>2d>2) possible neighbors, which are sampled from the set of the existing vertices with the probability proportional to their degrees. It is known that the maximum of the degree distribution in this model has linear behavior. We prove that kk-th highest dergee has a sublinear behavior with a power depends on dd. This contrasts sharply with what is seen in the preferential attachment model without choice, where all highest degrees in the degree distribution has the same sublinear order. The proof is based on showing that the considered tree has a persistent hub by comparison with the standard preferential attachment model, along with martingale arguments.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.