Data compression for sparse labeled graphs
Shannon entropy, in its simplest interpretation, concerns data compression where the data
is a long string from a finite alphabet: assuming a stationary source of entropy \(\mathcal{E}\),
a length-\(n\) string can be coded as a binary string of length about \(\mathcal{E} n\).
Consider instead a sparse (\(O(1)\) average degree) \(n\)-vertex graph, whose vertices are labeled by
distinct length-\(O(\log n) \) strings from a finite alphabet.
The entropy of the graph structure and the entropy of the labels are typically both of order \(n \log n\).
Are there universal codes analogous to Lempel-Ziv
for asymptotically optimal compression of such labeled graphs?
We raised the question in this paper
but made no progress.