☆

1

An improvement to Boldi-Vigna WebGraph. It uses Huffman coding, asymmetric numeral systems (a form of arithmetic coding) and a new hybrid integer encoding schema.
The paper also mentions other algorithms like [Log(Graph) by Besta et al.](https://www.youtube.com/watch?v=j98N9nthr0M) and Apostolico-Drovandi method together with $k^2$-trees, 2D block trees, ZipG graph store... Author suggest the [Besta-Hoefler survey (2018) with more than 460 references](https://arxiv.org/abs/1806.01799) to any reader interested in lossless graph compression methods.
The paper does not consider node permutations.
The code is in [google's github account](https://github.com/google/zuckerli).

☆

1

Furthermore, Apostolico and Drovandi suggest to use $\pi$-code, see Section 4 from [their paper](https://papers-gamma.link/paper/178), when the power law distribution have an exponent close to 1.
It actually pushes me to ask, maybe a naive question: is there any standard method to construct such a code when the distribution of the gaps is given or estimated from the data?

☆

3

Clever algorithm. The java code is [available on the net](https://github.com/drovandi/GraphCompressionByBFS).
In 2009, it was almost simultaneously published with [Permuting Web and Social Graphs](https://papers-gamma.link/paper/177) of Boldi et al.
At this time it is better than Boldi et al. solution in many cases.
The Apostolico-Drovandi paper is mentioned as "The only coordinate-free compression algorithm we are aware of"
in [another](https://papers-gamma.link/paper/105) Boldi et al. paper which was published after a while. At that time Boldi et al. provide better results.

## Comments: