Shrink: Distance preserving graph compression

Publication Year: 2017 Publication Type : JournalArticle


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 4.7 million nodes is reduced to fifth while the average relative error is less than 3%.


    author = {Amin Sadri and Flora D. Salim and Yongli Ren and Masoomeh Zameni and Jeffrey Chan and Timos Sellis},
    bibsource = {dblp computer science bibliography,},
    biburl = {},
    doi = {10.1016/},
    journal = {Inf. Syst.},
    pages = {180--193},
    timestamp = {Sat, 19 Oct 2019 01:00:00 +0200},
    title = {Shrink: Distance preserving graph compression},
    url = {},
    volume = {69},
    year = {2017}


Related Publications

RUP: Large Room Utilisation Prediction with carbon dioxide sensor
Type : JournalArticle
Show More
A Scalable Room Occupancy Prediction with Transferable Time Series Decomposition of CO 2 Sensor Data
Type : JournalArticle
Show More
Topical Event Detection on Twitter
Type : ConferenceProceeding
Show More

© 2021 Flora Salim - CRUISE Research Group.