Large-scale behavior of the partial duplication random graph

MaRDI QIDQ2818772zbMATH OpenFDO

Authors Felix Hermann, Peter Pfaffelhuber

Publication date 8 September 2016

Published in ALEA. Latin American Journal of Probability and Mathematical Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.0904, http://alea.impa.br/articles/v13/13-27.pdf

zbMATH Keywords

degree distributionduality of Markov processesrandom graph

Mathematics Subject Classification ID

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

Abstract: The following random graph model was introduced for the evolution of protein-protein interaction networks: Let $mathcalG=(G_n{)}_{n=n_0,n_0+1,\mathrm{...}}$ be a sequence of random graphs, where $G_n=(V_n,E_n)$ is a graph with $|V_n|=n$ vertices, $n=n_0,n_0+1,\mathrm{...}$ In state $G_n=(V_n,E_n)$, a vertex $vin{V}_n$ is chosen from $V_n$ uniformly at random and is partially duplicated. Upon such an event, a new vertex $v^{\prime }otin{V}_n$ is created and every edge $v,win{E}_n$ is copied with probability~$p$, i.e. $E_{n+1}$ has an edge $v^{\prime },w$ with probability~$p$, independently of all other edges. Within this graph, we study several aspects for large~$n$. (i) The frequency of isolated vertices converges to~1 if $pleq{p}^{\ast }approx0.567143$, the unique solution of $p{e}^p=1$. (ii) The number $C_k$ of $k$-cliques behaves like $n^{k{p}^{k-1}}$ in the sense that $n^{-k{p}^{k-1}}{C}_k$ converges against a non-trivial limit, if the starting graph has at least one $k$-clique. In particular, the average degree of a vertex (which equals the number of edges -- or 2-cliques -- divided by the size of the graph) converges to $0$ iff $p<0.5$ and we obtain that the transitivity ratio of the random graph is of the order $n^{-2p(1-p)}$. (iii) The evolution of the degrees of the vertices in the initial graph can be described explicitly. Here, we obtain the full distribution as well as convergence results.

Recommendations

• The partial duplication random graph with edge deletion
• Degree distribution of large networks generated by the partial duplication model
• The connected component of the partial duplication graph
• Asymptotic properties of a random graph with duplications
• Further properties of a random graph with duplications and deletions

Cited in

(12)

• Products of normal, beta and gamma random variables: Stein operators and distributional theory
• 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
• Asymptotic properties of a random graph with duplications
• Preferential duplication graphs
• The connected component of the partial duplication 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
• Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple
• On the Concentration of the Maximum Degree in the Duplication-Divergence Models

This page was built for publication: Large-scale behavior of the partial duplication random graph

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