A Rust implementation of the WebGraph framework for graph compression.
-
Compressed graph representation (start from here):
webgraph(repo) -
Algorithms:
webgraph-algo(repo) -
CLI commands:
webgraph-cli(repo)
There are Python bindings for WebGraph.
-
A detailed description of the compression algorithms used in WebGraph, published in the proceedings of the Thirteenth International World–Wide Web Conference.
-
A mathematical analysis of the performance of γ, δ and ζ codes against power-law distributions.
-
Some quite surprising experiments showing that the transpose graph reacts very peculiarly to compression after lexicographical or Gray-code sorting.
-
A paper about HyperBall (then named HyperANF), our tool for computing an approximation of the neighbourhood function, reachable nodes and geometric centralities of massive graphs. More information can be found in this preprint.
-
HyperBall was used to find out that on average there are just four degrees of separation on Facebook, and the experiment was reported by the New York Times. Alas, the degrees were actually 3.74 (one less than the average distance), but the off-by-one between graph theory (“distance”) and sociology (“degrees of separation”) generated a lot of confusion.
-
A paper were we describe our efforts to compress one of the largest social graphs available—the graph of commits of the Software Heritage archive.
This software has been partially supported by project SERICS (PE00000014) under the NRRP MUR program funded by the EU - NGEU, and by project ANR COREGRAPHIE, grant ANR-20-CE23-0002 of the French Agence Nationale de la Recherche. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the Italian MUR. Neither the European Union nor the Italian MUR can be held responsible for them.