WebGraph

WebGraph 框架的 Rust 实现，用于图压缩。

WebGraph 是一个针对图压缩的框架，旨在研究网络图，但目前正被应用于多种其他类型的图。它提供了简单的方式来管理非常大的图，利用现代压缩技术。更具体地说，它目前包括

• 一组简单的代码，称为 ζ 代码，特别适合存储网络图（或更一般地说，在某个指数范围内的幂律分布的整数）。

• 压缩网络图的算法，利用间隙压缩和差分压缩（类似于 LINK），区间化和 ζ 代码，以提供高压缩比（参见 我们的数据集）。算法受多个参数控制，这些参数在访问速度和压缩比之间提供不同的权衡。

• 访问压缩图而不实际解压缩的算法，使用延迟解压缩的懒加载技术，直到实际需要时才进行解压缩。

• 分析非常大的图的算法，例如 HyperBall，该算法已被用于证明 Facebook 只有 四度分隔。

• 上述算法的 Java 实现，现在处于维护模式。

• 此 crate 提供了上述算法的完整、文档化的 Rust 实现。它是自由软件，在 GNU Lesser General Public License 2.1+ 或 Apache 软件许可证 2.0 下分发。

• 大型图（例如，数十亿个链接）的 数据集

引用

欢迎您使用和改进 WebGraph 用于您的研究工作！如果您觉得我们的软件对研究有用，请在您的论文中引用以下论文：

• “WebGraph: The Next Generation (Is in Rust)”，由 Tommaso Fontana、Sebastiano Vigna 和 Stefano Zacchiroli 撰写，发表在 WWW '24: Companion Proceedings of the ACM on Web Conference 2024 上，第 686–689 页。 DOI 10.1145/3589335.3651581。

• “《WebGraph框架I：压缩技术》”，作者Paolo Boldi和Sebastiano Vigna，载于《第13届国际万维网会议论文集》（WWW 2004），第595–602页，ACM。DOI 10.1145/988672.988752。。

快速设置

假设您已构建所有二进制文件，您首先需要一个以BV格式表示的图，例如从LAW网站下载。对于一个基名为BASENAME的图，您需要以下文件：BASENAME.graph（包含图的压缩表示的字节流）文件、BASENAME.properties（元数据）文件和BASENAME.offsets（包含指向图字节流中指针的字节流）文件。

作为第一步，如果您需要随机访问一个节点的后继节点，您需要构建偏移量的Elias-Fano表示（如果您只需要顺序访问，则可跳过此部分）。有一个名为webgraph的命令行界面，其中包含许多子命令，其中包括build，而webgraph build ef BASENAME将为您构建表示，并以BASENAME.ef命名的文件使用ε-serde进行序列化。

然后，要加载图，您需要调用

let graph = BVGraph::with_basename("BASENAME").load()?;

with_basename方法返回一个LoadConfig实例，可以进一步自定义，选择端序、内存访问类型等。默认情况下，您将获得大端序、图和偏移量的内存映射以及动态代码调度。

请注意，在Windows上，内存映射需要图文件长度是内部位缓冲区的倍数。您可以使用命令行命令run pad u32确保您的图文件正确填充。

加载图后，您可以检索节点的后继节点或遍历整个图。特别是，使用方便的for_宏，您可以将图遍历编写为

for_!((src, succ) in graph {
    for dst in succ {
        [do something with the arc src -> dst]
    }
});

命令行界面

我们提供命令行界面以执行对图的多种操作。CLI是库的主要方法，因此可以通过cargo run执行。

更多选项

• 从BVGraphSeq类开始，您可以获取一个不需要BASENAME.ef文件的实例，但仅提供迭代。

• 图可以通过与zipping它们结合使用labeling来进行标记。实际上，图只是具有usize标签的标记。