Further properties of a random graph with duplications and deletions

DOI10.1080/15326349.2015.1088789zbMATH Open1338.05240arXiv1409.5279OpenAlexW1588578190MaRDI QIDQ2803405FDOQ2803405

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

Publication date: 4 May 2016

Published in: Stochastic Models (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (7)

• Insertion-tolerance and repetitiveness of random graphs
• Randomised reproducing graphs
• A time-invariant random graph with splitting events
• The connected component of the partial duplication graph
• Preferential duplication graphs
• Infinite limits and adjacency properties of a generalized copying model
• The partial duplication random graph with edge deletion

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)