###
Extended Compact Web Graph Representations

####
Francisco Claude and Gonzalo Navarro

Many relevant Web mining tasks translate into classical algorithms on the Web
graph. Compact Web graph representations allow running these tasks on larger
graphs within main memory. These representations at least provide fast
navigation (to the neighbors of a node), yet more sophisticated operations are
desirable for several Web analyses.
We present a compact Web graph representation that, in addition, supports
reverse navigation (to the nodes pointing to the given one).
The standard approach to achieve this is to represent the graph and its
transpose, which basically doubles the space requirement. Our structure,
instead, represents the adjacency list using a compact sequence representation
that allows finding the positions where a given node *v* is mentioned, and
answers reverse navigation using that primitive. This is combined with a
previous proposal based on grammar compression of the adjacency list. The
combination yields interesting algorithmic problems.
As a result, we achieve the smallest graph representation reported in the
literature that supports direct and reverse navigation, and also obtain other
variants that occupy relevant niches in the space/time tradeoff.