Succinct Preferential Attachment Graphs

In this paper, we show that a simple degree-entropy based compression algorithm is asymptotically instance-optimal for the class of preferential attachment graphs, and can be used as an instance-optimal compressed data structure.

To support queries on the graph, such as adjacency, degree, and neighborhood queries (all in logarithmic time), we store its adjacency list as an entropy-compressed wavelet tree. For unlabeled graphs, we first remove a carefully chosen spanning tree, which is stored as a succinct tree and gives vertices new labels, thus reducing the overall space almost by $\lg n$ bits per vertex.