A random mapping with preferential attachment

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

Abstract

In this article we investigate the asymptotic structure of a random mapping model with preferential attachment, Tn?, which maps the set {1,2,. . . , n} into itself. The model Tn? was introduced in a companion article [Hansen and Jaworski, Random Struct Algorithms 33 (2008), 105-126] and the asymptotic structure of the associated directed graph Gn? which represents the action of Tn? on the set {1,2, . . . , n} was investigated in [Hansen and Jaworski, Random Struct Algorithms 33 (2008), 105-126] and [Hansen and Jaworski, Adv Appl Probab 40 (2008), 183-205] in the case when the attraction parameter ? > 0 is fixed as n ? 8. In this article we consider the asymptotic structure of Gn? when the attraction parameter ? = ?(n) is a function of n as n ? 8. We show that there are three distinct regimes during the evolution of G n? (i) ?n ? 8 as n ? 8, (ii)?n ? ß > 0 as n ? 8, and (iii) ?n ? 0 as n ? 8. It turns out that the asymptotic structure of G n? is, in some cases, quite different from the asymptotic structure of well-known models such as the uniform random mapping model and models with an attracting center. In particular, in regime (ii) we obtain some interesting new limiting distributions which are related to the incomplete gamma function. © 2008 Wiley Periodicals, Inc.

Original languageEnglish
Pages (from-to)87-111
Number of pages25
JournalRandom Structures and Algorithms
Volume34
Issue number1
DOIs
Publication statusPublished - Jan 2009
Event13th International Conference on Random Structures and Algorithms - Tel Aviv, Israel
Duration: 28 May 20071 Jun 2007

Keywords

  • Component structure
  • Evolution
  • Exchangeable in-degrees
  • Preferential attachment
  • Random mappings

Fingerprint Dive into the research topics of 'A random mapping with preferential attachment'. Together they form a unique fingerprint.

  • Cite this