Simple view
Full metadata view
Authors
Statistics
Compression of dynamic graphs generated by a duplication model
random graphs
structural entropy
graph compression
duplication model
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).
cris.lastimport.scopus | 2024-04-07T16:42:02Z | |
dc.abstract.en | 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). | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |
dc.contributor.author | Turowski, Krzysztof - 425506 | pl |
dc.contributor.author | Magner, Abram | pl |
dc.contributor.author | Szpankowski, Wojciech | pl |
dc.date.accessioned | 2020-10-30T10:44:54Z | |
dc.date.available | 2020-10-30T10:44:54Z | |
dc.date.issued | 2020 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.physical | 2687-2707 | pl |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 82 | pl |
dc.identifier.doi | 10.1007/s00453-020-00699-2 | pl |
dc.identifier.eissn | 1432-0541 | pl |
dc.identifier.issn | 0178-4617 | pl |
dc.identifier.project | UMO-2016/21/B/ST6/03146 | pl |
dc.identifier.project | ROD UJ / OP | pl |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/251905 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
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.subject.en | random graphs | pl |
dc.subject.en | structural entropy | pl |
dc.subject.en | graph compression | pl |
dc.subject.en | duplication model | pl |
dc.subtype | Article | pl |
dc.title | Compression of dynamic graphs generated by a duplication model | pl |
dc.title.journal | Algorithmica | pl |
dc.type | JournalArticle | pl |
dspace.entity.type | Publication |
* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.
Views
0
Views per month
Downloads
Open Access
License
Except as otherwise noted, this item is licensed under the Attribution 4.0 International licence