Shrink: Distance preserving graph compression

作者：

Highlights：

• We present a graph compression method that preserves distances between the nodes.

• It is applicable to weighted and unweighted graphs (e.g. road and social network).

• Distance-based queries can be run without decompression.

• The user can control a trade-off between accuracy and compression ratio.

• The complexity is linear in the number of nodes, |V|, when the average degree σ ≪|V|.

摘要

•We present a graph compression method that preserves distances between the nodes.•It is applicable to weighted and unweighted graphs (e.g. road and social network).•Distance-based queries can be run without decompression.•The user can control a trade-off between accuracy and compression ratio.•The complexity is linear in the number of nodes, |V|, when the average degree σ ≪|V|.

论文关键词：Graph compression,Graph simplification,Graph databases,Shortest paths

论文评审过程：Received 10 January 2017, Revised 19 April 2017, Accepted 1 June 2017, Available online 7 June 2017, Version of Record 15 June 2017.

论文官网地址：https://doi.org/10.1016/j.is.2017.06.001