文章基本信息

标题：Power-Law Degree Distribution in the Connected Component of a Duplication Graph
本地全文：下载
作者：Philippe Jacquet ; Krzysztof Turowski ; Wojciech Szpankowski 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：159
页码：16:1-16:14
DOI：10.4230/LIPIcs.AofA.2020.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：random graphs; pure duplication model; degree distribution; tail exponent; analytic combinatorics