Compression of Dynamic Graphs Generated by a Duplication Model
Krzysztof Turowski, Abram Magner, Wojciech Szpankowski · 2018
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 a constant term. Interestingly, for the full duplication model the labeled version needs Θ(n) bits while its unlabeled version (structure) can be described by Θ(log n) bits due to a significant amount of symmetry (i.e., the cardinality of the automorphism group of graphs generated by this model is on average quite high).