A random mapping with preferential attachment

DOI10.1002/RSA.20251MaRDI QIDQ3608314zbMATH OpenOpenAlexFDO

Authors Jennie C. Hansen, Jerzy Jaworski

Publication date 4 March 2009

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603529

zbMATH Keywords

evolutionpreferential attachmentcomponent structureexchangeable in-degreesrandom mapping

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Exchangeability for stochastic processes (60G09)

Abstract: We introduce a new random mapping model, $T_n^{hatD}$, which maps the set $1,2,\mathrm{...},n$ into itself.The random mapping $T_n^{hatD}$ is constructed using a collection of exchangeable random variables $hat{D}_1,\mathrm{....},hat{D}_n$ which satisfy $su{m}_{i=1}^{n}hat{D}_i=n$. In the random digraph,$G_n^{hatD}$, which represents the mapping $T_n^{hatD}$, the in-degree sequence for the vertices is given by the variables $hat{D}_1,hat{D}_2,\mathrm{...},hat{D}_n$, and, in some sense,$G_n^{hatD}$ can be viewed as an analogue of the general independent degree models from random graph theory. We show that the distribution of the number of cyclic points, the number of components,and the size of a typical component can be expressed in terms of expectations of various functions of $hat{D}_1,hat{D}_2,\mathrm{...},hat{D}_n$. We also consider two special examples of $T_n^{hatD}$ which correspond to random mappings with preferential and anti-preferential attachment, respectively, and determine, for these examples, exact and asymptotic distributions for the statistics mentioned above.

Recommendations

• Random mappings with exchangeable in-degrees
• Local properties of random mappings with exchangeable in-degrees
• Predecessors and successors in random mappings with exchangeable in-degrees
• The asymptotic degree distribution of a kind of evolving random tree
• scientific article; zbMATH DE number 4107819

Cites work

• scientific article; zbMATH DE number 3860065 (Why is no real title available?)
• scientific article; zbMATH DE number 1380606 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• A cutting process for random mappings
• Brownian bridge asymptotics for random \(p\)-mappings
• Cycles in a Uniform Graph Process
• Epidemic processes on digraphs of random mappings
• Limits of logarithmic combinatorial structures.
• On a simple formula for random mappings and its applications
• On random mappings with a single attracting centre
• Order statistics for decomposable combinatorial structures
• Random Mappings with a Single Attracting Center
• Random mappings with an attracting center: Lagrangian distributions and a regression function
• Random mappings with exchangeable in-degrees
• The largest connected component in a random mapping
• Total variation asymptotics for Poisson process approximations for logarithmic combinatorial assemblies
• Weak convergence of random p-mappings and the exploration process of inhomogeneous continuum random trees

Cited in

(7)

• Limit theorems for the logarithm of the order of a random \(A\)-mapping
• A Turán-Kubilius inequality on mappings of a finite set
• Predecessors and successors in random mappings with exchangeable in-degrees
• Distance between two random \(k\)-out digraphs, with and without preferential attachment
• GHS algorithm on a graph with random weights
• Random mappings with exchangeable in-degrees
• Local properties of random mappings with exchangeable in-degrees

This page was built for publication: A random mapping with preferential attachment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608314)