Predecessors and successors in random mappings with exchangeable in-degrees

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

In this paper we characterise the distributions of the number of predecessors and of the number of successors of a given set of vertices, A, in the random mapping model, T-n((D) over cap) (see Hansen and Jaworski (2008)), with exchangeable in-degree sequence ((D) over bar (1), (D) over bar (2), ..., (D) over bar (n)). We show that the exact formulae for these distributions and their expected values can be given in terms of the distributions of simple functions of the in-degree variables (D) over bar (1), (D) over bar (2), ..., (D) over bar (n). As an application of these results, we consider two special examples of T-n(D) over bar which correspond to random mappings with preferential and anti-preferential attachment, and determine the exact distributions for the number of predecessors and the number of successors in these cases. We also characterise, for these two special examples, the asymptotic behaviour of the expected numbers of predecessors and successors and interpret these results in terms of the threshold behaviour of epidemic processes on random mapping graphs. The families of discrete distributions obtained in this paper are also of independent interest.

Original languageEnglish
Pages (from-to)721-740
Number of pages20
JournalJournal of Applied Probability
Volume50
Issue number3
Publication statusPublished - Sep 2013

Keywords

  • Random mapping
  • exchangeable in-degrees
  • preferential attachment
  • anti-preferential attachment
  • urn scheme
  • epidemic process
  • RANDOM GRAPH
  • ATTRACTING CENTER
  • DISTRIBUTIONS

Cite this