3 releases
new 0.1.2  Jul 31, 2024 

0.1.1  Jul 31, 2024 
0.1.0  Mar 17, 2023 
#185 in Compression
227 downloads per month
3MB
11K
SLoC
WebGraph
A Rust implementation of the WebGraph framework for graph compression.
WebGraph is a framework for graph compression aimed at studying web graphs, but currently being applied to several other types of graphs. It provides simple ways to manage very large graphs, exploiting modern compression techniques. More precisely, it is currently made of:

A set of simple codes, called ζ codes, which are particularly suitable for storing web graphs (or, in general, integers with a powerlaw distribution in a certain exponent range).

Algorithms for compressing web graphs that exploit gap compression and differential compression (à la LINK), intervalization, and ζ codes to provide a high compression ratio (see our datasets). The algorithms are controlled by several parameters, which provide different tradeoffs between access speed and compression ratio.

Algorithms for accessing a compressed graph without actually decompressing it, using lazy techniques that delay the decompression until it is actually necessary.

Algorithms for analyzing very large graphs, such as HyperBall, which has been used to show that Facebook has just four degrees of separation.

A Java implementation of the algorithms above, now in maintenance mode.

This crate, providing a complete, documented implementation of the algorithms above in Rust. It is free software distributed under either the GNU Lesser General Public License 2.1+ or the Apache Software License 2.0.

Data sets for large graphs (e.g., billions of links).
Citation
You are welcome to use and improve WebGraph for your research work! If you find our software useful for research, please cite the following papers in your own:

“WebGraph: The Next Generation (Is in Rust)”, by Tommaso Fontana, Sebastiano Vigna, and Stefano Zacchiroli, in WWW '24: Companion Proceedings of the ACM on Web Conference 2024, pages 686–689. DOI 10.1145/3589335.3651581.

“The WebGraph Framework I: Compression Techniques”, by Paolo Boldi and Sebastiano Vigna, in Proc. of the 13th international conference on World Wide Web, WWW 2004, pages 595–602, ACM. DOI 10.1145/988672.988752.
Quick Setup
Assuming you have built all binaries, you will first need a graph in BV format,
for example downloading it from the LAW website. For a graph with basename
BASENAME
, you will need the BASENAME.graph
file (the bitstream containing a
compressed representation of the graph), the BASENAME.properties
file
(metadata), and the BASENAME.offsets
file (a bitstream containing pointers into
the graph bitstream).
As a first step, if you need random access to the successors of a node, you need
to build an Elias–Fano representation of the offsets (this part can be skipped
if you just need sequential access). There is a CLI command webgraph
with many
subcommands, among which build
, and webgraph build ef BASENAME
will build
the representation for you, serializing it with εserde in a file
named BASENAME.ef
.
Then, to load the graph you need to call
let graph = BVGraph::with_basename("BASENAME").load()?;
The with_basename
method returns a LoadConfig
instance that can be
further customized, selecting endianness, type of memory access, and so on. By
default you will get big endianness, memory mapping for both the graph and the
offsets, and dynamic code dispatch.
Note that on Windows memory mapping requires that the length of the graph file
is a multiple of the internal bit buffer. You can use the CLI command run pad u32
to ensure that your graph file is properly padded.
Once you load the graph, you can retrieve the successors of a node or
iterate on the whole graph. In particular, using the handy for_
macro,
you can write an iteration on the graph as
for_!((src, succ) in graph {
for dst in succ {
[do something with the arc src > dst]
}
});
Command–Line Interface
We provide a commandline interface to perform various operations on graphs. The
CLI is the main method of the library, so it can be executed with cargo run
.
More Options

By starting from the
BVGraphSeq
class you can obtain an instance that does not need theBASENAME.ef
file, but provides only iteration. 
Graphs can be labeled by zipping them together with a labeling. In fact, graphs are just labelings with
usize
labels.
Operating on Graphs
There are many operations available on graphs, such as transpose, simplify, and permute.
Acknowledgments
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 ANR20CE230002 of the French Agence Nationale de la Recherche.
Dependencies
~24–61MB
~1M SLoC