Communications in Information and Systems

Volume 22 (2022)

Number 2

Compression and symmetry of small-world graphs and structures

Pages: 275 – 302

DOI: https://dx.doi.org/10.4310/CIS.2022.v22.n2.a5

Authors

Ioannis Kontoyiannis (Statistical Laboratory, Centre for Mathematical Sciences, University of Cambridge, United Kingdom)

Yi Heng Lim (Department of Engineering, University of Cambridge, United Kingdom)

Katia Papakonstantinopoulou (Department of Informatics, Theory, Economics and Systems Laboratory, Athens University of Economics and Business, Athens, Greece)

Wojtek Szpankowski (Department of Computer Science, Purdue University, West Lafayette, Indiana, U.S.A.)

Abstract

For various purposes and, in particular, in the context of data compression, a graph can be examined at three levels. Its structure can be described as the unlabelled version of the graph; then the labelling of its structure can be added; and finally, given then structure and labelling, the contents of the labels can be described. Determining the amount of information present at each level and quantifying the degree of dependence between them requires the study of symmetry, graph automorphism, entropy, and graph compressibility. In this paper, we focus on a class of small-world graphs. These are geometric random graphs where vertices are first connected to their nearest neighbours on a circle and then pairs of non-neighbours are connected according to a distance-dependent probability distribution. We establish the degree distribution of this model, and use it to prove the model’s asymmetry in an appropriate range of parameters. Then we derive the relevant entropy and structural entropy of these random graphs, in connection with graph compression.

Keywords

entropy, information, lossless compression, random graph, random network, small-world graph, graphical structure, symmetry

2010 Mathematics Subject Classification

Primary 60Fxx, 94A15. Secondary 05C80.

Full Text (PDF format)

I.K. was supported in part by NSF Center for Science of Information (CSoI) Grant CCF-0939370, and in addition by NSF Grants CCF-1524312, CCF-2006440, and CCF-2007238.

K.P. was supported in part by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant,” project number 1034.

Received 13 July 2021

Published 19 May 2022