2025/01/19 by Tiffany Y. Y. Lo, Lo, Tiffany Y. Y., Gesine Reinert +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #FOS: Mathematics #Probability (math.PR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2501.11077
openalex publication_date 2025/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Duplication-divergence models are a popular model for the evolution of gene and protein interaction networks. However, existing duplication-divergence models often neglect realistic features such as loss of interactions. Thus, in this paper we present two novel models that incorporate random edge deletions into the duplication-divergence framework. As in protein-protein interaction networks, with proteins as vertices and interactions as edges, by design isolated vertices tend to be rare, our main focus is on the number of isolated vertices; our main result gives lower and upper bounds for the proportion of isolated vertices, when the network size is large. Using these bounds we identify the parameter regimes for which almost all vertices are typically isolated; and also show that there are parameter regimes in which the proportion of isolated vertices can be bounded away from 0 and 1 with high probability. In addition, we find regimes in which the proportion of isolated vertices tends to be small. The proof relies on a standard martingale argument, which in turn requires a careful analysis of the first two moments of the expected degree distribution. The theoretical findings are illustrated by simulations, indicating that as the network size tends to infinity, the proportion of isolated vertices can converge to a limit that is neither 0 or 1.