Compressibility of Voter-Model State Snapshots in the Graph Spectral Basis

The sparsity or compressibility of network spread states in a graph-spectrum basis is examined, in the context of a stochastic model for influence/spread known as the voter model. In particular, the first- and second-moments are characterized, for the graph-spectrum basis components contained in the voter-model state. These formal characterizations, as well as an asymptotic analysis of the voter model, are used to relate compressibility with the network's graph. An illustrative example as well as a simulation of a larger-scale model are included.