### Abstract

In this article we investigate the asymptotic structure of a random mapping model with preferential attachment, T_{n}^{?}, which maps the set {1,2,. . . , n} into itself. The model T_{n}^{?} 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 G_{n}^{?} which represents the action of T_{n}^{?} 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 G_{n}^{?} 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 language | English |
---|---|

Pages (from-to) | 87-111 |

Number of pages | 25 |

Journal | Random Structures and Algorithms |

Volume | 34 |

Issue number | 1 |

DOIs | |

Publication status | Published - Jan 2009 |

Event | 13th International Conference on Random Structures and Algorithms - Tel Aviv, Israel Duration: 28 May 2007 → 1 Jun 2007 |

### Fingerprint

### Keywords

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

### Cite this

*Random Structures and Algorithms*,

*34*(1), 87-111. https://doi.org/10.1002/rsa.20251

}

*Random Structures and Algorithms*, vol. 34, no. 1, pp. 87-111. https://doi.org/10.1002/rsa.20251

**A random mapping with preferential attachment.** / Hansen, Jennie C.; Jaworski, Jerzy.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A random mapping with preferential attachment

AU - Hansen, Jennie C.

AU - Jaworski, Jerzy

N1 - The research in this paper was supported by the Marie Curie Intra-European Fellowship No. 501863 (RANDIGRAPH) within the 6th European Community Framework Programme.

PY - 2009/1

Y1 - 2009/1

N2 - 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.

AB - 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.

KW - Component structure

KW - Evolution

KW - Exchangeable in-degrees

KW - Preferential attachment

KW - Random mappings

UR - http://www.scopus.com/inward/record.url?scp=60349103215&partnerID=8YFLogxK

U2 - 10.1002/rsa.20251

DO - 10.1002/rsa.20251

M3 - Article

VL - 34

SP - 87

EP - 111

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 1

ER -