Further properties of a random graph with duplications and deletions

DOI10.1080/15326349.2015.1088789MaRDI QIDQ2803405zbMATH OpenOpenAlexFDO

Authors Tamás F. Móri, Ágnes Backhausz

Publication date 4 May 2016

Published in Stochastic Models (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.5279, http://real.mtak.hu/33575/1/1409.5279v1.pdf

zbMATH Keywords

deletionrandom graphsduplicationscale freemaximal degree

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Strong limit theorems (60F15)

Abstract: We deal with a random graph model where at each step, a vertex is chosen uniformly at random, and it is either duplicated or its edges are deleted. Duplication has a given probability. We analyse the limit distribution of the degree of a fixed vertex, and derive a.s. asymptotic bounds for the maximal degree. The model shows a phase transition phenomenon with respect to the probabilities of duplication and deletion.

Recommendations

• Asymptotic properties of a random graph with duplications
• The partial duplication random graph with edge deletion
• Asymptotic degree distribution of a duplication-deletion random graph model
• On the degree sequence of an evolving random graph process and its critical phenomenon
• Phase transition on the degree sequence of a random graph process with vertex copying and deletion

Cites work

• A survey of random processes with reinforcement
• An introduction to stochastic modeling.
• Asymptotic properties of a random graph with duplications
• Emergence of Scaling in Random Networks
• On a 2-parameter class of scale free random graphs
• On a preferential attachment and generalized Pólya's urn model
• Polya Urn Models
• Power laws for family sizes in a duplication model
• Preferential duplication graphs
• Random networks with sublinear preferential attachment: degree evolutions
• Randomised reproducing graphs
• Robust analysis of preferential attachment models with fitness
• Splitting trees with neutral Poissonian mutations. I: Small families
• Splitting trees with neutral Poissonian mutations. II: Largest and oldest families
• The Maximum Degree of the Barabási–Albert Random Tree
• The degree distribution of the generalized duplication model
• Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph
• Transition of the degree sequence in the random graph model of Cooper, Frieze, and Vera
• Weighing the ``heaviest Polya urn
• Weights and degrees in a random graph model based on 3-interactions

Cited in

(13)

• The partial duplication random graph with edge deletion
• Towards degree distribution of a duplication-divergence graph model
• The split-and-drift random graph, a null model for speciation
• Insertion-tolerance and repetitiveness of random graphs
• Randomised reproducing graphs
• Asymptotic properties of a random graph with duplications
• A time-invariant random graph with splitting events
• The connected component of the partial duplication graph
• On the Concentration of the Maximum Degree in the Duplication-Divergence Models
• Preferential duplication graphs
• Infinite limits and adjacency properties of a generalized copying model
• Large-scale behavior of the partial duplication random graph
• Asymptotic degree distribution of a duplication-deletion random graph model

This page was built for publication: Further properties of a random graph with duplications and deletions

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