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

Sébastien Bubeck, Elchanan Mossel, Miklós Z. Rácz

Research output: Contribution to journalArticlepeer-review

33 Scopus citations

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.

Original languageEnglish (US)
Article number7024931
Pages (from-to)30-39
Number of pages10
JournalIEEE Transactions on Network Science and Engineering
Volume2
Issue number1
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Random trees
  • preferential attachment
  • seed graph

Fingerprint

Dive into the research topics of 'On the influence of the seed graph in the preferential attachment model'. Together they form a unique fingerprint.

Cite this