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.
Spectral methods have also been successfully applied to graph ordering problems @cite_19 . Sequencing the vertices is done by sorting them according to corresponding elements of the second smallest eigenvector of graph Laplacian (also called the Fiedler vector). It is known that the order yields the best non-trivial solution to a relaxation of the quadratic graph ordering problem , and hence, it is a good heuristic for computing linear arrangements.
@cite_19
2004265962
Abstract For several NP-hard optimal linear labeling problems, including the bandwidth, the cutwidth, and the min-sum problem for graphs, a heuristic algorithm is proposed which finds approximative solutions to these problems in polynomial time. The algorithm uses eigenvectors corresponding to the second smallest Laplace eigenvalue of a graph. Although bad in some “degenerate” cases, the algorithm shows fairly good behaviour. Several upper and lower bounds on the bandwidth, cutwidth, and min- p -sums are derived. Most of these bounds are given in terms of Laplace eigenvalues of the graphs. They are used in the analysis of our algorithm and as measures for the error of the obtained approximation to an optimal labeling.