License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.16
URN: urn:nbn:de:0030-drops-120467
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12046/
Jacquet, Philippe ;
Turowski, Krzysztof ;
Szpankowski, Wojciech
Power-Law Degree Distribution in the Connected Component of a Duplication Graph
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.
BibTeX - Entry
@InProceedings{jacquet_et_al:LIPIcs:2020:12046,
author = {Philippe Jacquet and Krzysztof Turowski and Wojciech Szpankowski},
title = {{Power-Law Degree Distribution in the Connected Component of a Duplication Graph}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {16:1--16:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Michael Drmota and Clemens Heuberger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12046},
URN = {urn:nbn:de:0030-drops-120467},
doi = {10.4230/LIPIcs.AofA.2020.16},
annote = {Keywords: random graphs, pure duplication model, degree distribution, tail exponent, analytic combinatorics}
}
|
Keywords: |
|
random graphs, pure duplication model, degree distribution, tail exponent, analytic combinatorics |
|
Collection: |
|
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
10.06.2020 |
