A Fuzzy Low-Dimensional Intersection Graph Representation Approach for Graph Compression and Anonymization

Abstract

The large amount of data represented as a network, or graph, sometimes exceeds the resources of a conventional computing device. In particular, links in a network consume a great portion of memory in comparison to the number of nodes. Even if the graph were to be completely stored on disk with the aid of virtual memory, I/O operations would require exhaustive computing power as opposed to queries that consult the main memory. However, rigorous edge storage is not always necessary to extract useful information and meaningful insights. In this context, we propose a fuzzy lowdimensional representation by mapping any given graph onto a k-dimensional space such that the distance between any two nodes determines their adjacency status. The proposed mapping utilizes an intersection graph representation where k-dimensional balls represent the nodes, and the likelihood of adjacency of two nodes is measured by whether the corresponding balls intersect. The objective is to answer adjacency queries as accurately as possible and to achieve an effective compression. We examine several heuristic algorithms in an attempt to achieve these two main objectives and conduct a thorough experimental analysis providing evidence of the effectiveness of our graph mapping approach. An additional perk of this work is the capability of completely hiding private information in networks.