The power of 2 choices over preferential attachment
classification
🧮 math.PR
math.CO
keywords
degreeattachmentchoicesgraphpreferentialprobabilityvertexachlioptas
read the original abstract
We introduce a new type of preferential attachment tree that includes choices in its evolution, like with Achlioptas processes. At each step in the growth of the graph, a new vertex is introduced. Two possible neighbor vertices are selected independently and with probability proportional to degree. Between the two, the vertex with smaller degree is chosen, and a new edge is created. We determine with high probability the largest degree of this graph up to some additive error term.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.