Distributed Compression of Graphical Data.

In contrast to time series, graphical data is data indexed by the nodes andedges of a graph. Modern applications such as the internet, social networks,genomics and proteomics generate graphical data, often at large scale. Thelarge scale argues for the need to compress such data for storage andsubsequent processing. Since this data might have several components availablein different locations, it is also important to study distributed compressionof graphical data. In this paper, we derive a rate region for this problemwhich is a counterpart of the Slepian-Wolf Theorem. We characterize the rateregion when the statistical description of the distributed graphical data isone of two types - a marked sparse Erdos-Renyi ensemble or a markedconfiguration model. Our results are in terms of a generalization of the notionof entropy introduced by Bordenave and Caputo in the study of local weak limitsof sparse graphs.