CUED Publications database

Compression and Symmetry of Small-World Graphs and Structures

Kontoyiannis, I and Lim, YH and Papakonstantinopoulou, K and Szpankowski, W Compression and Symmetry of Small-World Graphs and Structures. (Unpublished)

Full text not available from this repository.


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 unlabeled version of the graph; then the labeling of its structure can be added; and finally, given then structure and labeling, 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 neighbors on a circle and then pairs of non-neighbors 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.

Item Type: Article
Uncontrolled Keywords: cs.IT cs.IT math.CO math.IT math.PR
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 06 Aug 2020 03:09
Last Modified: 25 Aug 2020 01:30