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.
Confronting The Reality Of US Broadband Performance - [image: broadband]*Editor's note:* *Richard Bennett is a Senior Fellow with the Information Technology and Innovation Foundation and co-author of ITIF’s 20...
36 minutes ago