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.
@article{10_37236_9251,
author = {Krzysztof Turowski and Wojciech Szpankowski},
title = {Towards degree distribution of a duplication-divergence graph model},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/9251},
zbl = {1456.05160},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9251/}
}
TY - JOUR
AU - Krzysztof Turowski
AU - Wojciech Szpankowski
TI - Towards degree distribution of a duplication-divergence graph model
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9251/
DO - 10.37236/9251
ID - 10_37236_9251
ER -
%0 Journal Article
%A Krzysztof Turowski
%A Wojciech Szpankowski
%T Towards degree distribution of a duplication-divergence graph model
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9251/
%R 10.37236/9251
%F 10_37236_9251
Krzysztof Turowski; Wojciech Szpankowski. Towards degree distribution of a duplication-divergence graph model. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9251
