GraphRox is a network graph library for efficiently generating approximations of graphs. GraphRox additionally provides a high-fidelity, lossy graph compression algorithm.
See https://docs.rs/graphrox/latest/graphrox/ for documentation on using the library in Rust.
Using the Library
To use the library in Rust, add it to
[dependencies] graphrox = "1.1"
GraphRox is available on PyPi, so you can install the package with:
pip3 install graphrox
And then you can import it:
import graphrox as gx
After downloading and building GraphRox from source (with
cargo build —release), a static library and a dynamic link library will each be produced in the
target/release directory. C code can link to the GraphRox library statically using the compile library and the
gphrx.h header from the
graphrox-c directory, or dynamically using the DLL.
How it works
The approximation algorithm applies average pooling to a graph's adjacency matrix to construct an approximation of the graph. The approximation will have a lower dimensionality than the original graph. The adjacency matrix will be partitioned into blocks of a specified of dimension and then the matrix entries within each partition will be average pooled. A given threshold will be applied to the average pooled entries such that each entry that is greater than or equal to the threshold will become a 1 in the adjacency matrix of the resulting approximate graph. Average pooled entries that are lower than the threshold will become zeros in the resulting approximate graph. The graph's adjacency matrix will be padded with zeros if a block to be average pooled does not fit withing the adjacency matrix.
Using the same approximation technique mentioned above, a threshold is applied to 8x8 blocks in a graph's adjacency matrix. If a given block in the matrix meets the threshold, the entire block will be losslessly encoded in an unsigned 64-bit integer. If the block does not meet the threshold, the entire block will be represented by a 0 in the resulting matrix. Because GraphRox stores matrices as adjacency lists, 0 entries have no effect on storage size.
A threshold of 0.0 is essentially a lossless compression.
Testing and Building the Library
The GraphRox library is written in Rust. Building it produces two artifacts: 1) a
Rust library that Rust programs can statically link to and 2) a dynamic link library (a
.so file on Linux,
.dylib on macOS, or
.dll on Windows) with a C ABI. These
artifacts get placed in the
./target directory, relative to the top-level of the
To build the library, you need to have the
Rust Toolchain installed. From the project
cargo build --release to build the Binaries.
To run unit tests, run
cargo test. To generate formatted documentation, run