Wei Liu
ABSTRACT
Existing graph compression techniquesmostly focus on static graphs. However for many practical graphs such as social networks the edge weights frequently change over time. This phenomenon raises the question of how to compress dynamic graphs while maintaining most of their intrinsic structural patterns at each time snapshot. In this paper we show that the encoding cost of a dynamic graph is proportional to the heterogeneity of a three dimensional tensor that represents the dynamic graph. We propose an effective algorithm that compresses a dynamic graph by reducing the heterogeneity of its tensor representation, and at the same time also maintains a maximum lossy compression error at any time stamp of the dynamic graph. The bounded compression error benefits compressed graphs in that they retain good approximations of the original edge weights, and hence properties of the original graph (such as shortest paths) are well preserved. To the best of our knowledge, this is the first work that compresses weighted dynamic graphs with bounded lossy compression error at any time snapshot of the graph.
- T. Cover and J. Thomas. Elements of Information. John Wiley & Sons, New Jersey, 2006.Google Scholar
- A. Fernández and S. Gómez. Solving non-uniqueness in agglomerative hierarchical clustering. Journal of Classification, 25(1):43--65, 2008. Google ScholarDigital Library
- B. Klimt and Y. Yang. Introducing the enron corpus. In Proc of CEAS 2004.Google Scholar
- H. Maserrat and J. Pei. Neighbor query friendly compression of social networks. In Proc of KDD 2010. Google ScholarDigital Library
- S. Navlakha, R. Rastogi, and N. Shrivastava. Graph summarization with bounded error. In Proc of SIGMOD 2008. Google ScholarDigital Library
- H. Toivonen, F. Zhou, A. Hartikainen, and A. Hinkka. Compression of weighted graphs. In Proc of KDD 2011. Google ScholarDigital Library
- I. H. Witten, R. M. Neal, and J. G. Cleary. Arithmetic coding for data compression. Commun. ACM, 30(6):520--540, 1987. Google ScholarDigital Library
- F. Zhou, S. Malher, and H. Toivonen. Network simplification with minimal loss of connectivity. In Proc of ICDM 2010. Google ScholarDigital Library
Index Terms
- On compressing weighted time-evolving graphs
Recommendations
Lossy Compression of Dynamic, Weighted Graphs
FICLOUD '15: Proceedings of the 2015 3rd International Conference on Future Internet of Things and CloudA graph is used to represent data in which the relationships between the objects in the data are at least as important as the objects themselves. Large graph datasets are becoming more common as networks such as the Internet grow, and our ability to ...
Antimagic labelling of vertex weighted graphs
Suppose G is a graph, k is a non-negative integer. We say G is k-antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted-k-antimagic if for any vertex weight function w: V→ℕ, ...
Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient domination problem is the problem of finding an efficient dominating set ...
Comments