Rate-Distortion Function of the Stochastic Block Model
Martin Wachiye Wafula, Praneeth Kumar Vippathalla, Justin P. Coon, Mihai-Alin Badiu · 2023
The stochastic block model (SBM) is extensively used to model networks in which users belong to certain communities. In recent years, the study of information-theoretic compression of such networks has gained attention, with works primarily focusing on lossless compression. In this work, we address the lossy compression of SBM graphs by characterizing the rate-distortion function under a Hamming distortion constraint. Specifically, we derive the conditional rate-distortion function of the SBM with community membership as side information to both the encoder and decoder. We approach this problem as the classical Wyner-Ziv lossy problem by minimising mutual information of the graph and its reconstruction conditioned on community labels. Lastly, we also derive the rate-distortion function of the Erdὄs-Rényl (ER) random graph model.