solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看171次
An Information-theoretic Framework for the Lossy Compression of Link Streams. (arXiv:1807.06874v1 [cs.DS])
来源于:arXiv
Graph compression is a data analysis technique that consists in the
replacement of parts of a graph by more general structural patterns in order to
reduce its description length. It notably provides interesting exploration
tools for the study of real, large-scale, and complex graphs which cannot be
grasped at first glance. This article proposes a framework for the compression
of temporal graphs, that is for the compression of graphs that evolve with
time. This framework first builds on a simple and limited scheme, exploiting
structural equivalence for the lossless compression of static graphs, then
generalises it to the lossy compression of link streams, a recent formalism for
the study of temporal graphs. Such generalisation relies on the natural
extension of (bidimensional) relational data by the addition of a third
temporal dimension. Moreover, we introduce an information-theoretic measure to
quantify and to control the information that is lost during compression, as
well as an alge 查看全文>>