  Computing the product of the (binary) adjacency matrix of a large graph with
a real-valued vector is an important operation that lies at the heart of
various graph analysis tasks, such as computing PageRank. In this paper we show
that some well-known Web and social graph compression formats are
computation-friendly, in the sense that they allow boosting the computation. In
particular, we show that the format of Boldi and Vigna allows computing the
product in time proportional to the compressed graph size. Our experimental
results show speedups of at least 2 on graphs that were compressed at least 5
times with respect to the original. We show that other successful graph
compression formats enjoy this property as well.
