2023/09/25 by Martin Wachiye Wafula, Praneeth Kumar Vippathalla, Wafula, Martin Wachiye +5
Mathematics · Computer Science · #Random Matrices and Applications #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2309.14464
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. 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ényi (ER) random graph model.