Speeding up Algorithms on Compressed Web Graphs

Speeding up Algorithms on Compressed Web Graphs is a Microsoft paper @ WSDM09, which leverages a smart tranformation for compressing the Web graph. The idea is pretty simple: an heuristic based on frequent itemset mining is used for tranforming cliques into stars connections.
As a consequences, the number of edges can be drammatically reduced at the cost of introducing some new virtual node.

The paper then introduce an optimized matrix-vector multiplication which reoders the adjencency matrix of the tranformed Web graph. This multiplication is then used to speed-up PageRank, Hits and Salsa on the compressed graph.