论文标题
压缩Erdös-rényi图的类型大小代码
Type Size Code for Compressing Erdös-Rényi Graphs
论文作者
论文摘要
我们考虑了通常称为图形结构的未标记图的通用源编码。我们采用Erdös-Rényi模型来生成随机图形结构。我们提出了先前引入的类型大小代码的变体，其中类型类是根据图形结构的边数进行表征的。提出的方案根据其类型类的大小对图形结构进行分类，并按照此顺序为其分配二进制序列。得出了压缩图形结构的类型大小代码的$ε$编码速率（最多三阶项）。
We consider universal source coding of unlabeled graphs which are commonly referred to as graphical structures. We adopt an Erdös-Rényi model to generate the random graphical structures. We propose a variant of the previously introduced Type Size code, where type classes are characterized based on the number of edges of the graphical structures. The proposed scheme sorts the graphical structures based on the size of their type classes and assigns binary sequences to them in this order. The $ε$-coding rate of the Type Size code (up to the third-order term) for compressing graphical structures is derived.
