Exploiting Computation-Friendly Graph Compression Methods for
Adjacency-Matrix Multiplication
Alexandre Francisco, Travis Gagie, Susana Ladra, and Gonzalo Navarro
Computing the product of the adjacency (binary) 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.