On the Influence of the Seed Graph in the Preferential Attachment Model

被引：31

作者：

Bubeck, Sebastien ^{[1
]}

Mossel, Elchanan ^{[2
,3
]}

Racz, Miklos Z. ^{[3
]}

机构：

[1] Princeton Univ, Princeton, NJ 08544 USA

[2] Univ Penn, Philadelphia, PA 19104 USA

[3] Univ Calif Berkeley, Berkeley, CA 94703 USA

来源：

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING | 2015年 / 2卷 / 01期

基金：

美国国家科学基金会;

关键词：

Random trees; preferential attachment; seed graph;

D O I：

10.1109/TNSE.2015.2397592

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

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.

引用

页码：30 / 39

页数：10

共 16 条

[11] The maximum degree of the Barabasi-Albert random tree [J].