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

Fingerprint

Random Mapping
Preferential Attachment
Incomplete gamma Function
Model
Limiting Distribution
Directed Graph
Distinct

Keywords

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

Cite this

Hansen, Jennie C. ; Jaworski, Jerzy. / A random mapping with preferential attachment. In: Random Structures and Algorithms. 2009 ; Vol. 34, No. 1. pp. 87-111.
@article{0222e67d76c84213864eb469a8a5104b,
title = "A random mapping with preferential attachment",
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 ? {\ss} > 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. {\circledC} 2008 Wiley Periodicals, Inc.",
keywords = "Component structure, Evolution, Exchangeable in-degrees, Preferential attachment, Random mappings",
author = "Hansen, {Jennie C.} and Jerzy Jaworski",
note = "The research in this paper was supported by the Marie Curie Intra-European Fellowship No. 501863 (RANDIGRAPH) within the 6th European Community Framework Programme.",
year = "2009",
month = "1",
doi = "10.1002/rsa.20251",
language = "English",
volume = "34",
pages = "87--111",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Ltd",
number = "1",

}

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

In: Random Structures and Algorithms, Vol. 34, No. 1, 01.2009, p. 87-111.

Research output: Contribution to journalArticle

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 -