论文标题
小世界图和结构的压缩和对称性
Compression and Symmetry of Small-World Graphs and Structures
论文作者
论文摘要
出于各种目的，尤其是在数据压缩的背景下，可以在三个级别检查图。它的结构可以描述为图形的未标记版本。然后可以添加其结构的标签；最后，可以描述标签的内容和标记，可以描述标签的内容。确定每个级别上存在的信息量并量化它们之间的依赖程度，需要研究对称性，图形自动形态，熵和图形可压缩性。在本文中，我们专注于一类小世界图。这些是几何随机图，其中首先将顶点连接到其最近的邻居，然后根据距离依赖性的概率分布连接成对的非邻域。我们建立了该模型的度分布，并使用它来证明模型的不对称性在适当的参数范围内。然后，我们将这些随机图的相关熵和结构熵与图形压缩有关。
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.
