Succinct Preferential-Attachment Graphs

Jun 2025 (Written: Feb 2024)

Ziad Ismaili Alaoui, Namrata, and Sebastian Wild:

International Workshop on Graph-Theoretic Concepts in Computer Science 2025

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.

our data structure for unlabeled PA graphs — Our data structure for unlabeled preferential-attachment graphs. Each vertex originally has outdegree $M=3$. One of these edges is stored within $T$, the others explicitly in the wavelet tree for $A'$.

Relation to other papers

A generalization of the data structure for arbitrary unlabeled graphs (and the study of the ensuing optimization problem) is presented in our follow-up work.