Graph Compression for Adjacency-Matrix Multiplication
Use este enlace para citar
http://hdl.handle.net/2183/31180Coleccións
- GI-LBD - Artigos [32]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Graph Compression for Adjacency-Matrix MultiplicationData
2022Cita bibliográfica
Francisco, A.P., Gagie, T., Köppl, D. et al. Graph Compression for Adjacency-Matrix Multiplication. SN COMPUT. SCI. 3, 193 (2022). https://doi.org/10.1007/s42979-022-01084-2
Resumo
[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 well-known 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.
Palabras chave
Matrix multiplication
Webgraph
Bicliques
Data compression
Webgraph
Bicliques
Data compression
Descrición
19 April 2022
A Correction to this paper has been published: https://doi.org/10.1007/s42979-022-01141-w
Versión do editor
Dereitos
Atribución 3.0 España