Papers^γ / Sergey Kirgizov

Hello, are you aware of any open source implementation of this algorithm ?

Some nice presentations on the topic: - https://www.irif.fr/~habib/Documents/cours_4-2015.pdf - http://igm.univ-mlv.fr/AlgoB/algoperm2012/04Paul.pdf - http://www.lirmm.fr/~paul/Talks/talk-06-algo-sem-McGill.pdf

>See table 3 from https://arxiv.org/abs/1811.10705 This is with $n=50$ nodes. It seems that the behavior is not the same for $n$ large: - I think that in a large ER, if the proba of connection $p$ is not too large or too small, then it is rare to find a group of nodes with the same neighbors outside the group (i.e. find a module). Can you prove that? - I don't think that the code https://github.com/antonovvk/decmod is buggy.

[Almost all finite graphs are asymmetric](https://en.wikipedia.org/wiki/Asymmetric_graph#Random_graphs). There is no pair of vertices with common neighborhood.

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).

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?