Compressing bipartite graphs with a dual reordering scheme - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... (Preprint) Year :

Compressing bipartite graphs with a dual reordering scheme

(1) , (1) , (1)


In order to manage massive graphs in practice, it is often necessary to resort to graph compression, which aims at reducing the memory used when storing and processing the graph. Efficient compression methods have been proposed in the literature, especially for web graphs. In most cases, they are combined with a vertex reordering pre-processing step which significantly improves the compression rate. However, these techniques are not as efficient when considering other kinds of graphs. In this paper, we focus on the class of bipartite graphs and adapt the vertex reordering phase to their specific structure by proposing a dual reordering scheme. By reordering each group of vertices in the purpose of minimizing a specific score, we show that we can reach better compression rates. We also suggest that this approach can be further refined to make the node orderings more adapted to the compression phase that follows the ordering phase. * Authors contribution: MD proposed the original idea of the paper, IP realized the codes and experiments, IP and LT contributed equally to the analysis and the writing of the paper.
Fichier principal
Vignette du fichier
2209.12062.pdf (232.82 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03875560 , version 1 (28-11-2022)


  • HAL Id : hal-03875560 , version 1


Maximilien Danisch, Ioannis Panagiotas, Lionel Tabourier. Compressing bipartite graphs with a dual reordering scheme. 2022. ⟨hal-03875560⟩
0 View
0 Download


Gmail Facebook Twitter LinkedIn More