• Mathematics of computing → Random graphs
  • Theory of computation → Random network models
Philippe Jacquet
INRIA, Saclay - Île-de-France, France
Krzysztof Turowski
Theoretical Computer Science Department, Jagiellonian University, Krakow, Poland
Wojciech Szpankowski
Center for Science of Information, Department of Computer Science, Purdue University, West Lafayette, IN, USA

Abstract. We study the partial duplication dynamic graph model, introduced by Bhan et al. in [Bhan et al., 2002] in which a newly arrived node selects randomly an existing node and connects with probability p to its neighbors. Such a dynamic network is widely considered to be a good model for various biological networks such as protein-protein interaction networks. This model is discussed in numerous publications with only a few recent rigorous results, especially for the degree distribution. Recently Jordan [Jordan, 2018] proved that for 0 < p < 1/e the degree distribution of the connected component is stationary with approximately a power law. In this paper we rigorously prove that the tail is indeed a true power law, that is, we show that the degree of a randomly selected node in the connected component decays like C/k^β where C an explicit constant and β ≠ 2 is a non-trivial solution of p^(β-2) + β - 3 = 0. This holds regardless of the structure of the initial graph, as long as it is connected and has at least two vertices. To establish this finding we apply analytic combinatorics tools, in particular Mellin transform and singularity analysis.

This work was supported by NSF Center for Science of Information (CSoI) Grant CCF-0939370, in addition by NSF Grant CCF-1524312, and National Science Center, Poland, Grant 2018/31/B/ST6/01294.