View publication

Title Graph Compression for Adjacency-Matrix Multiplication
Authors Alexandre Francisco, Travis Gagie, Dominik Koppl, Susana Ladra, Gonzalo Navarro
Publication date 2022
Abstract 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 wellknown webgraph and social graph compression formats are computation-friendly, in the sense that they allow boosting the
computation. We focus on the compressed representations of (a) Boldi and Vigna and (b) Hernández and Navarro, and show
that the product computation can be conducted 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.
Pages article 193
Volume 3
Journal name SN Computer Science
Publisher Springer (New York, NY, USA)
Reference URL View reference page