Towards degree distribution of a duplication-divergence graph model

2021
journal article
article
2
cris.lastimport.wos2024-04-10T01:47:35Z
dc.abstract.enWe present a rigorous and precise analysis of degree distribution in a dynamic graph model introduced by Sol ́e, Pastor-Satorras et al. in which nodes are added according to a duplication-divergence mechanism. This model is discussed in nu- merous 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.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorTurowski, Krzysztof - 425506 pl
dc.contributor.authorSzpankowski, Wojciechpl
dc.date.accession2024-05-13
dc.date.accessioned2021-03-24T11:28:57Z
dc.date.available2021-03-24T11:28:57Z
dc.date.issued2021pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number1pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume28pl
dc.identifier.articleidP1.18pl
dc.identifier.doi10.37236/9251pl
dc.identifier.eissn1077-8926pl
dc.identifier.issn1097-1440pl
dc.identifier.project2018/31/B/ST6/01294pl
dc.identifier.projectNSF Grants CCF-1524312, CCF-2006440, CCF-2007238pl
dc.identifier.projectGrant CCF- 0939370pl
dc.identifier.projectROD UJ / Opl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/267985
dc.identifier.weblinkhttps://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i1p18/pdf
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa
dc.rights.licenceCC-BY-ND
dc.rights.simpleviewWolny dostęp
dc.rights.urihttps://creativecommons.org/licenses/by-nd/4.0/legalcode.pl
dc.share.typeotwarte czasopismo
dc.subtypeArticlepl
dc.titleTowards degree distribution of a duplication-divergence graph modelpl
dc.title.journalThe Electronic Journal of Combinatoricspl
dc.typeJournalArticlepl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-10T01:47:35Z
dc.abstract.enpl
We present a rigorous and precise analysis of degree distribution in a dynamic graph model introduced by Sol ́e, Pastor-Satorras et al. in which nodes are added according to a duplication-divergence mechanism. This model is discussed in nu- merous 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.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.authorpl
Turowski, Krzysztof - 425506
dc.contributor.authorpl
Szpankowski, Wojciech
dc.date.accession
2024-05-13
dc.date.accessioned
2021-03-24T11:28:57Z
dc.date.available
2021-03-24T11:28:57Z
dc.date.issuedpl
2021
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
1
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
28
dc.identifier.articleidpl
P1.18
dc.identifier.doipl
10.37236/9251
dc.identifier.eissnpl
1077-8926
dc.identifier.issnpl
1097-1440
dc.identifier.projectpl
2018/31/B/ST6/01294
dc.identifier.projectpl
NSF Grants CCF-1524312, CCF-2006440, CCF-2007238
dc.identifier.projectpl
Grant CCF- 0939370
dc.identifier.projectpl
ROD UJ / O
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/267985
dc.identifier.weblink
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i1p18/pdf
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights
Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa
dc.rights.licence
CC-BY-ND
dc.rights.simpleview
Wolny dostęp
dc.rights.uri
https://creativecommons.org/licenses/by-nd/4.0/legalcode.pl
dc.share.type
otwarte czasopismo
dc.subtypepl
Article
dc.titlepl
Towards degree distribution of a duplication-divergence graph model
dc.title.journalpl
The Electronic Journal of Combinatorics
dc.typepl
JournalArticle
dspace.entity.type
Publication

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
11
Views per month
Views per city
Krakow
4
Ashburn
3
Wroclaw
2
Dublin
1