The partial duplication random graph with edge deletion

MaRDI QIDQ5856499zbMATH OpenFDO

Authors Felix Hermann, Peter Pfaffelhuber

Publication date 26 March 2021

Full work available at URL https://arxiv.org/abs/1904.00718, http://alea.impa.br/articles/v18/18-15.pdf

zbMATH Keywords

cliquesdegree distributionrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study a random graph model in continuous time. Each vertex is partially copied with the same rate, i.e. an existing vertex is copied and every edge leading to the copied vertex is copied with independent probability $p$. In addition, every edge is deleted at constant rate, a mechanism which extends previous partial duplication models. In this model, we obtain results on the degree distribution, which shows a phase transition such that either -- if $p$ is small enough -- the frequency of isolated vertices converges to 1, or there is a positive fraction of vertices with unbounded degree. We derive results on the degrees of the initial vertices as well as on the sub-graph of non-isolated vertices. In particular, we obtain expressions for the number of star-like subgraphs and cliques.

Recommendations

• Further properties of a random graph with duplications and deletions
• Large-scale behavior of the partial duplication random graph
• Asymptotic degree distribution of a duplication-deletion random graph model
• Asymptotic properties of a random graph with duplications
• The connected component of the partial duplication graph
• Publication:4508361
• Copies of the random graph
• Analysis of edge deletion processes on faulty random regular graphs.
• On classes of infinite loaded graphs with randomly deleted edges
• Expansion properties of a random regular graph after random vertex deletions

Cites work

• A general model of web graphs
• Degree distribution for duplication-divergence graphs: large deviations
• Evolution of the social network of scientific collaborations
• Evolving protein interaction networks through gene duplication
• Handbook of large-scale random networks
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• scientific article; zbMATH DE number 7651055 (Why is no real title available?)
• Large-scale behavior of the partial duplication random graph
• Markov branching processes with disasters: extinction, survival and duality to p-jump processes
• Random graph dynamics
• Random graphs and complex networks. Volume 1
• The connected component of the partial duplication graph
• The degree distribution of the generalized duplication model
• The split-and-drift random graph, a null model for speciation

Cited in

(8)

• Degree distribution of large networks generated by the partial duplication model
• Further properties of a random graph with duplications and deletions
• Large-scale behavior of the partial duplication random graph
• Asymptotic properties of a random graph with duplications
• The connected component of the partial duplication graph
• Asymptotic degree distribution of a duplication-deletion random graph model
• The expected degree distribution in transient duplication divergence models
• Phase transition on the degree sequence of a random graph process with vertex copying and deletion

This page was built for publication: The partial duplication random graph with edge deletion

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