Abstract
We present a rigorous and precise analysis of degree distribution in a dynamic graph model introduced by Solé, Pastor-Satorras et al. in which nodes are added according to a duplication-divergence mechanism. This model is discussed in numerous publications with only very few recent rigorous results, especially for the degree distribution. In this paper we focus on two related problems: the expected value and variance of the degree of a given node over the evolution of the graph and the expected value and variance of the average degree over all nodes. We present exact and precise asymptotic results showing that both quantities may decrease or increase over time depending on the model parameters. Our findings are a step towards a better understanding of the graph behaviors such as degree distributions, symmetry, power law, and structural compression.
Introduction
The evolution of real-world networks, such as protein-protein interaction (PPI) networks and citation graphs, is often driven by mechanisms more complex than simple random attachment. One of the most prominent models for such growth is the duplication-divergence (DD) mechanism, originally proposed by Solé and Pastor-Satorras. In this model, a new node enters the network as a copy of an existing node (duplication), followed by a divergence step where connections are either lost or new ones are added.
Despite its widespread use in bioinformatics and network science for nearly two decades, the DD model has largely been analyzed through empirical simulations or non-rigorous heuristics. This paper addresses this gap by providing a rigorous mathematical analysis of the degree distribution, specifically focusing on the expected degree of nodes and the average degree of the graph as it evolves over time.
Methodology
The authors employ a combination of probabilistic modeling and analytic combinatorics to derive exact and asymptotic results. The core of the analysis involves:
- Recurrence Relations: Deriving exact recurrences for the expected degree of a specific node $s$ at time $t$, denoted as $\mathbb{E}[\text{deg}_t(s)]$, and the average degree of the entire graph, $\mathbb{E}[D(G_t)]$.
- Martingale Theory: Utilizing a generalized version of a lemma from stochastic process literature to solve these complex recurrences.
- Asymptotic Analysis: Applying Gamma functions and generalized hypergeometric functions ($_{3}F_{2}$) to determine the growth rates as the graph size $t \to \infty$.
Key Insights and Phase Transitions
The analysis identifies the parameter $p$ (the probability of retaining an edge during divergence) as the primary driver of the graph's structural evolution. The parameter $r$ (the probability of adding random new edges) primarily influences the constants rather than the fundamental growth rates.
Average Degree Growth
The graph's average degree exhibits three distinct regimes based on the value of $p$:
- Sparse Regime ($p < 1/2$): The average degree remains bounded, $\mathbb{E}[D(G_t)] = \Theta(1)$.
- Critical Point ($p = 1/2$): The average degree grows logarithmically, $\mathbb{E}[D(G_t)] = \Theta(\log t)$.
- Dense Regime ($p > 1/2$): The average degree grows polynomially, $\mathbb{E}[D(G_t)] = \Theta(t^{2p-1})$.
The Influence of the Seed Graph
A significant finding is that the initial "seed graph" ($G_{t_0}$) leaves a permanent mark on the network's final structure. Unlike many other dynamic graph models where the initial state is eventually forgotten, the seed graph in the DD model strictly influences the leading constants of the degree distribution.
Node Age and Connectivity
The paper quantifies a "rich-get-richer" effect. In the dense regime ($p > 1/2$), older nodes (those added early in the process) experience much faster degree growth than younger nodes. However, the scaling laws derived here are distinct from those found in traditional preferential attachment models, offering a new perspective on how "hubs" form in biological networks.
Variance and Volatility
The authors also provide results for the variance of these quantities, revealing another phase transition at $p = \sqrt{2}-1 \approx 0.414$. If $p$ exceeds this value, the variance of the degree of the newest node begins to grow polynomially, indicating significantly higher volatility in node connectivity as the network expands.
Conclusion
This research provides a rigorous foundation for understanding the first and second moments of the duplication-divergence model. While it clarifies the expected behavior and variance, several open problems remain, including the derivation of the full degree distribution (the exact number of nodes with degree $k$) and the analysis of large deviations and higher moments (skewness and kurtosis). These findings represent a crucial step toward a complete structural characterization of duplication-divergence graphs.
Summary updated