Compression of dynamic graphs generated by a duplication model

2020
journal article
article
6
dc.abstract.enWe continue building up the information theory of non-sequential data structures such as trees, sets, and graphs. In this paper, we consider dynamic graphs generated by a full duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We ask how many bits are needed to describe the labeled and unlabeled versions of such graphs. We first estimate entropies of both versions and then present asymptotically optimal compression algorithms up to two bits. Interestingly, for the full duplication model the labeled version needs Θ(n) bits while its unlabeled version (structure) can be described by Θ(logn) bits due to significant amount of symmetry (i.e. large average size of the automorphism group of sample graphs).pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorTurowski, Krzysztof - 425506 pl
dc.contributor.authorMagner, Abrampl
dc.contributor.authorSzpankowski, Wojciechpl
dc.date.accessioned2020-10-30T10:44:54Z
dc.date.available2020-10-30T10:44:54Z
dc.date.issued2020pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.physical2687-2707pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume82pl
dc.identifier.doi10.1007/s00453-020-00699-2pl
dc.identifier.eissn1432-0541pl
dc.identifier.issn0178-4617pl
dc.identifier.projectUMO-2016/21/B/ST6/03146pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/251905
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeinne
dc.source.integratorfalse
dc.subject.enrandom graphspl
dc.subject.enstructural entropypl
dc.subject.engraph compressionpl
dc.subject.enduplication modelpl
dc.subtypeArticlepl
dc.titleCompression of dynamic graphs generated by a duplication modelpl
dc.title.journalAlgorithmicapl
dc.typeJournalArticlepl
dspace.entity.typePublication
dc.abstract.enpl
We continue building up the information theory of non-sequential data structures such as trees, sets, and graphs. In this paper, we consider dynamic graphs generated by a full duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We ask how many bits are needed to describe the labeled and unlabeled versions of such graphs. We first estimate entropies of both versions and then present asymptotically optimal compression algorithms up to two bits. Interestingly, for the full duplication model the labeled version needs Θ(n) bits while its unlabeled version (structure) can be described by Θ(logn) bits due to significant amount of symmetry (i.e. large average size of the automorphism group of sample graphs).
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.authorpl
Turowski, Krzysztof - 425506
dc.contributor.authorpl
Magner, Abram
dc.contributor.authorpl
Szpankowski, Wojciech
dc.date.accessioned
2020-10-30T10:44:54Z
dc.date.available
2020-10-30T10:44:54Z
dc.date.issuedpl
2020
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.physicalpl
2687-2707
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
82
dc.identifier.doipl
10.1007/s00453-020-00699-2
dc.identifier.eissnpl
1432-0541
dc.identifier.issnpl
0178-4617
dc.identifier.projectpl
UMO-2016/21/B/ST6/03146
dc.identifier.projectpl
ROD UJ / OP
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/251905
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licence
CC-BY
dc.rights.uri*
http://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.type
inne
dc.source.integrator
false
dc.subject.enpl
random graphs
dc.subject.enpl
structural entropy
dc.subject.enpl
graph compression
dc.subject.enpl
duplication model
dc.subtypepl
Article
dc.titlepl
Compression of dynamic graphs generated by a duplication model
dc.title.journalpl
Algorithmica
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations

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

Views
19
Views per month
Views per city
Ashburn
7
Dublin
2
Wroclaw
2
Downloads
turowski_et-al_compression_of_dynamic_graphs_generated_2020.pdf
136
turowski_et-al_compression_of_dynamic_graphs_generated_2020.odt
18