Data that have an intrinsic network structure are becoming increasingly common in various scientific applications. Compressing such data for storage or transmission is an important problem, especially since networks are increasingly large. From an information theoretic perspective, the limit to compression of a random graph is given by the Shannon entropy of its distribution. A relevant question is how much of the information content of a random graph pertains to its structure (i.e., the unlabelled version of the graph), and how much of it is contained in the labels attached to the structure. Furthermore, in applications in which one is interested only in structural properties of a graph (e.g., node degrees, connectedness, frequency of occurrence of certain motifs), the node labels are irrelevant, such that only the structure of the graph needs to be compressed, leading to a more compact representation. In this talk, I will consider the random geometric graph (RGG), where pairs of nodes are connected based on the distance between them in some latent space. This model captures well important characteristics of biological systems, information networks, social networks, or economic networks. Since determination of the entropy is extremely difficult for this model, I will present upper bounds we obtained for the entropy of the labelled RGG. Then, we will focus on the structural information in the one-dimensional RGG. I will show our latest results in terms of the number of structures in the considered model and bounds on the structural entropy, together with the asymptotic behaviour of the bounds for different regimes of the connection range. Finally, I will also present a simple encoding scheme for one-dimensional RGG structures that asymptotically achieves the obtained upper limit on the structural entropy.
arXiv link: https://arxiv.org/abs/2107.13495