Succinct Preferential Attachment Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911024626532352 |
|---|---|
| author | Alaoui, Ziad Ismaili Namrata Wild, Sebastian |
| author_facet | Alaoui, Ziad Ismaili Namrata Wild, Sebastian |
| contents | Computing over compressed data combines the space saving of data compression with efficient support for queries directly on the compressed representation. Such data structures are widely applied in text indexing and have been successfully generalised to trees. For graphs, support for computing over compressed data remains patchy; typical results in the area of succinct data structures are restricted to a specific class of graphs and use the same, worst-case amount of space for any graph from this class.
In this work, we design a data structure whose space usage automatically improves with the compressibility of the graph at hand, while efficiently supporting navigational operations (simulating adjacency-list access). Specifically, we show that the space usage approaches the instance-optimal space when the graph is drawn according to the classic Barabási-Albert model of preferential-attachment graphs. Our data-structure techniques also work for arbitrary graphs, guaranteeing a size asymptotically no larger than an entropy-compressed edge list. A key technical contribution is the careful analysis of the instance-optimal space usage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21436 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Succinct Preferential Attachment Graphs Alaoui, Ziad Ismaili Namrata Wild, Sebastian Data Structures and Algorithms Information Theory Probability Computing over compressed data combines the space saving of data compression with efficient support for queries directly on the compressed representation. Such data structures are widely applied in text indexing and have been successfully generalised to trees. For graphs, support for computing over compressed data remains patchy; typical results in the area of succinct data structures are restricted to a specific class of graphs and use the same, worst-case amount of space for any graph from this class. In this work, we design a data structure whose space usage automatically improves with the compressibility of the graph at hand, while efficiently supporting navigational operations (simulating adjacency-list access). Specifically, we show that the space usage approaches the instance-optimal space when the graph is drawn according to the classic Barabási-Albert model of preferential-attachment graphs. Our data-structure techniques also work for arbitrary graphs, guaranteeing a size asymptotically no larger than an entropy-compressed edge list. A key technical contribution is the careful analysis of the instance-optimal space usage. |
| title | Succinct Preferential Attachment Graphs |
| topic | Data Structures and Algorithms Information Theory Probability |
| url | https://arxiv.org/abs/2506.21436 |