Abstract

By graphical data, we mean data indexed by the vertices and edges of a sparse graph rather than by linearly ordered time. Just as a stochastic process is a stochastic model for a time series got by picking a time index at random and viewing how the time series looks from that time index, in the local weak limit theory one studies graphical data by picking a node of the graph at random and seeing how the data looks from the point of view of that node. What results is a so-called sofic distribution on rooted marked graphs.

Bordenave and Caputo (2014) defined a notion of entropy for probability distributions on rooted graphs with finite expected degree at the root. We call this BC entropy. We develop the parallel result for probability distributions on marked rooted graphs. Our graphs have vertex marks drawn from a finite set and directed edge marks, one towards each vertex, drawn from a finite set.

We develop the details of our generalization of BC entropy to the case of rooted marked graphs. We then illustrate the value of this viewpoint by proving a universal lossless data compression theorem analogous to the basic universal lossless data compression theorem for time series. We also prove, for graphical data, an analog of the Slepian-Wolf theorem of distributed compression for Erdos-Renyi and configuration model ensembles.

This is joint work with Payam Delgosha.