On the discovery of the seed in uniform attachment trees

2018/10/01 by Devroye, Luc, Reddad, Tommy
#05C80 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Social and Information Networks (cs.SI) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1810.00969

Abstract

We investigate the size of vertex confidence sets for including part of (or the entirety of) the seed in seeded uniform attachment trees, given knowledge of some of the seed's properties, and with a prescribed probability of failure. We also study the problem of identifying the leaves of a seed in a seeded uniform attachment tree, given knowledge of the positions of all internal nodes of the seed.

Related

• Finding the seed of uniform attachment trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Leaf Stripping on Uniform Attachment Trees
• Vertices of high degree in the preferential attachment tree
• Influence of the seed in affine preferential attachment trees