The connected component of the partial duplication graph

MaRDI QIDQ4561260zbMATH OpenFDO

Authors Jonathan H. Jordan

Publication date 5 December 2018

Full work available at URL https://arxiv.org/abs/1712.06411, http://alea.impa.br/articles/v15/15-53.pdf

zbMATH Keywords

duplication graphquasi-stationary distribution

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of continuous-time Markov processes on discrete state spaces (60J28)

Abstract: We consider the connected component of the partial duplication model for a random graph, a model which was introduced by Bhan, Galas and Dewey as a model for gene expression networks. The most rigorous results are due to Hermann and Pfaffelhuber, who show a phase transition between a subcritical case where in the limit almost all vertices are isolated and a supercritical case where the proportion of the vertices which are connected is bounded away from zero. We study the connected component in the subcritical case, and show that, when the duplication parameter $p<e^{-1}$, the degree distribution of the connected component has a limit, which we can describe in terms of the stationary distribution of a certain Markov chain and which follows an approximately power law tail, with the power law index predicted by Ispolatov, Krapivsky and Yuryev. Our methods involve analysing the quasi-stationary distribution of a certain continuous time Markov chain associated with the evolution of the graph.

Recommendations

• The partial duplication random graph with edge deletion
• The connectivity of a bipartite graph and its bipartite complementary graph
• Dual of a complete graph as an interconnection network
• The connectivity of a graph and its complement
• The g-component connectivity of graphs
• The partial complement of graphs
• A partition of connected graphs
• A characterization of partially dual graphs
• Partial complementation of graphs

Cites work

• Asymptotic degree distribution of a duplication-deletion random graph model
• Asymptotic properties of a random graph with duplications
• Complex graphs and networks
• Degree distribution of large networks generated by the partial duplication model
• Emergence of Scaling in Random Networks
• Evolving protein interaction networks through gene duplication
• Further properties of a random graph with duplications and deletions
• Large-scale behavior of the partial duplication random graph
• Non-homogeneous random walks. Lyapunov function methods for near-critical stochastic systems
• Preferential duplication graphs
• Randomised reproducing graphs
• Reversibility, invariance and μ-invariance
• Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes
• The degree distribution of the generalized duplication model
• The degree sequence of a scale-free random graph process
• Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph

Cited in

(8)

• Degree distribution of large networks generated by the partial duplication model
• Towards degree distribution of a duplication-divergence graph model
• The concentration of the maximum degree in the duplication-divergence models
• Large-scale behavior of the partial duplication random graph
• The expected degree distribution in transient duplication divergence models
• The partial duplication random graph with edge deletion
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• On the Concentration of the Maximum Degree in the Duplication-Divergence Models

This page was built for publication: The connected component of the partial duplication graph

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