Introduction
WebGraph is a framework to study the web graph. It provides simple ways to manage
very large graphs, exploiting modern compression techniques. More precisely,
it is currently made of:
- A set of flat codes, called ζ codes, which are particularly suitable for storing web graphs (or, in general, integers with power-law distribution in a certain exponent range). The fact that these codes work well can be easily tested empirically, but we also try to provide a detailed mathematical analysis.
- Algorithms for compressing web graphs that exploit gap compression and referentiation (à la LINK), intervalisation and ζ codes to provide a high compression ratio: for instance, the WebBase graph (2001 crawl) is compressed at 3.08 bits per link, and a snapshot of about 18,500,000 pages of the .uk domain gathered by UbiCrawler is compressed at 2.22 bits per link (the corresponding figures for the transposed graphs are 2.89 bits per link and 1.98 bits per link). 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.
- A complete, documented implementation of the algorithms above in Java, contained in
the package
it.unimi.dsi.webgraph. Besides a clearly defined API, the package contains several classes that allow to modify (e.g., transpose) or recompress a graph, so to experiment with various settings. The package relies on fastutil 5 for a type-specific, high-performance collections framework, on MG4J for bit-level I/O, on the COLT distribution for ready-to-use, efficient algorithms and on JSAP for line-command parsing. - Datasets for very large graph (e.g., a billion of links). These are either gathered from public sources (such as WebBase), or produced by UbiCrawler.
In the end, with WebGraph you can access and analyse a very large web graph, even on a PC
with as little as 256 Mbytes of RAM. Using WebGraph is as easy as installing a few
jar files and downloading a dataset. This makes studying phenomena such as PageRank, distribution of
graph properties of the web graph, etc. very easy.
You are welcome to use and improve WebGraph! If you find our software useful for your research, please quote this paper.
Installation
For a quick start, you just have to install the
.jar file coming with the distribution and the dependencies, which are gathered for your convenience
in a tarball.
A more detailed list of the dependencies can be found in the overview of the Javadoc documentation. You may find useful to refer to the JPackage Project if you own an RPM-based distribution. In the same vein of the packages above, WebGraph is also distributed as a Jpackage-like RPM.
WebGraph++
Jacob Ratkievicz has developed a C++ version of WebGraph that you might want to try. The library exposes a BVGraph as an object of the Boost Graph Library, so it is easily integrable with other code.
pyWebgraph
Massimo Santini has developed a front-end that interfaces Jython with WebGraph. It makes exploring small portions of very large graphs very easy and interactive.