Graph reordering is a powerful technique to increase the locality of the representations of graphs, which can be helpful in several applications. We study how the technique can be used to improve compression of graphs and inverted indexes. We extend the recent theoretical model of (KDD 2009) for graph compression, and show how it can be employed for compression-friendly reordering of social networks and web graphs and for assigning document identifiers in inverted indexes. We design and implement a novel theoretically sound reordering algorithm that is based on recursive graph bisection. Our experiments show a significant improvement of the compression rate of graph and indexes over existing heuristics. The new method is relatively simple and allows efficient parallel and distributed implementations, which is demonstrated on graphs with billions of vertices and hundreds of billions of edges.
The three-step multiscale paradigm is often employed for the graph ordering problems. First, a sequence of coarsened graphs, each approximating the original graph but having a smaller size, is created. Then the problem is solved on the coarsest level by an exhaustive search. Finally, the process is reverted by an uncoarsening procedure so that a solution for every graph in the sequence is based on the solution for a previous smaller graph. Safro and Temkin @cite_7 employ the algebraic multigrid methodology in which the sequence of coarsened graphs is constructed using a projection of graph Laplacians into a lower-dimensional space.
@cite_7
2020378392
We present a fast multiscale approach for the network minimum logarithmic arrangement problem. This type of arrangement plays an important role in the network compression and fast node link access operations. The algorithm is of linear complexity and exhibits good scalability, which makes it practical and attractive for use in large-scale instances. Its effectiveness is demonstrated on a large set of real-life networks. These networks with corresponding best-known minimization results are suggested as an open benchmark for the research community to evaluate new methods for this problem.