Graph information ratio
Graph information ratio
复制标题
图信息比例
DOI：
10.1109/isit.2017.8006661
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
O. Shayevitz
中科院分区：
文献类型：
--
作者：
Lele Wang;O. Shayevitz
我们在两个（简单的、无向的）图 G 和 H 之间引入信息比 Ir(H/G) 的概念，它表征了每个通道使用的源符号的最大数量，这些符号可以通过具有混淆图 H 的通道可靠地发送，其中可靠性是用 w.r.t 来衡量的。提供了许多不同的结果，特别包括 Ir(H/G) 在各种图属性方面的下限和上限、强乘积和不相交联合下行为的不等式和恒等式、与图核心的关系以及图临界性的概念。非正式地说，Ir(H/G) 可以解释为 G 和 H 之间相似性的度量。我们通过引入图之间的信息等价概念（同态等价的更定量版本）使这个概念变得精确。然后，我们描述信息等价类空间上的自然偏序，并赋予它一个在强乘积下收缩的合适的度量结构。讨论了各种示例和直觉。
We introduce the notion of information ratio Ir(H/G) between two (simple, undirected) graphs G and H, which characterizes the maximal number of source symbols per channel use that can be reliably sent over a channel with confusion graph H, where reliability is measured w.r.t. a source confusion graph G. Many different results are provided, including in particular lower and upper bounds on Ir(H/G) in terms of various graph properties, inequalities and identities for behavior under strong product and disjoint union, relations to graph cores, and notions of graph criticality. Informally speaking, Ir(H/G) can be interpreted as a measure of similarity between G and H. We make this notion precise by introducing the concept of information equivalence between graphs, a more quantitative version of homomorphic equivalence. We then describe a natural partial ordering over the space of information equivalence classes, and endow it with a suitable metric structure that is contractive under the strong product. Various examples and intuitions are discussed.