Shrink: Distance preserving graph compression

The ever increasing size of graphs makes them difficult to query and store. In this paper, we present Shrink, a compression method that reduces the size of the graph while preserving the distances between the nodes. The compression is based on the iterative merging of the nodes. During each merging, a system of linear equations is solved to define new edge weights in a way that the new weights have the least effect on the distances. Merging nodes continues until the desired size for the compressed graph is reached. The compressed graph, also known as the coarse graph, can be queried without decompression. As the complexity of distance-based queries such as shortest path queries is highly dependent on the size of the graph, Shrink improves the performance in terms of time and storage. Shrink not only provides the length of the shortest path but also identifies the nodes on the path. The approach has been applied to both weighted and unweighted graphs including road network, friendship network, collaboration network, web graph and social network. In the experiment, a road network with more than 2.5 million nodes is reduced to fifth while the average relative error is less than 1%.

This repository contains resources - sample data and coding - developed for the paper of the same name.

图（graph）数据规模的持续增长，使其查询与存储均面临严峻挑战。本文提出Shrink算法，一种可在保留节点间距离的前提下压缩图体量的图压缩方法。该压缩基于节点迭代合并策略：每一轮合并过程中，通过求解线性方程组来确定新边权重，使新权重对节点间距离的影响降至最低。节点合并将持续进行，直至压缩后的图达到预设规模。这种压缩后的图亦被称为粗化图（coarse graph），可直接用于查询而无需提前解压。由于基于距离的查询（如最短路径查询）的复杂度高度依赖图的规模，Shrink可在存储与时间性能两方面实现优化。该算法不仅能够输出最短路径的长度，还可定位路径上的具体节点。此方法已被应用于加权与无权两类图结构，涵盖道路网络、好友关系网络、协作网络、网页图（web graph）以及社交网络。在实验中，一个包含超过250万个节点的道路网络被压缩至原规模的五分之一，且平均相对误差低于1%。

本仓库包含了为该同名论文开发的相关资源，即示例数据与代码实现。