A random mapping with preferential attachment

DOI10.1002/RSA.20251zbMATH Open1166.60004arXivmath/0603529OpenAlexW4234707618MaRDI QIDQ3608314FDOQ3608314

Authors: Jennie C. Hansen, Jerzy Jaworski 

Publication date: 4 March 2009

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Brownian bridge asymptotics for random \(p\)-mappings
• A cutting process for random mappings
• Random mappings with exchangeable in-degrees
• Order statistics for decomposable combinatorial structures
• On random mappings with a single attracting centre
• Random Mappings with a Single Attracting Center
• Random mappings with an attracting center: Lagrangian distributions and a regression function
• The largest connected component in a random mapping
• Title not available (Why is that?)
• Epidemic processes on digraphs of random mappings
• Limits of logarithmic combinatorial structures.
• Title not available (Why is that?)
• On a simple formula for random mappings and its applications
• Cycles in a Uniform Graph Process
• 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)