On the influence of the seed graph in the preferential attachment model

2014/01/20 by Sébastien Bubeck, Bubeck, Sébastien, Elchanan Mossel +3 · 1 citation
Computer Science · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Social and Information Networks (cs.SI) #Statistics Theory (math.ST) #cs.DM #cs.SI #math.PR #math.ST #stat.TH

paper · pdf · doi:10.48550/arxiv.1401.4849

arxiv created 2014/03/28 · arxiv updated 2014/03/31

Abstract

We study the influence of the seed graph in the preferential attachment model, focusing on the case of trees. We first show that the seed has no effect from a weak local limit point of view. On the other hand, we conjecture that different seeds lead to different distributions of limiting trees from a total variation point of view. We take a first step in proving this conjecture by showing that seeds with different degree profiles lead to different limiting distributions for the (appropriately normalized) maximum degree, implying that such seeds lead to different (in total variation) limiting trees.

Cited by

• Preferential Attachment Trees with Vertex Death: Persistence of the Maximum Degree

Related

• Influence of the seed in affine preferential attachment trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Vertices of high degree in the preferential attachment tree
• Condensation phenomena in preferential attachment trees with neighbourhood influence
• High degree vertices in the Power of Choice model combined with Preferential Attachment