论文标题
多维网络中的算法信息失真
An Algorithmic Information Distortion in Multidimensional Networks
论文作者
论文摘要
网络复杂性，网络信息内容分析以及图表的无损可压缩性在网络分析和网络建模中发挥了重要作用。随着多维网络（例如时变，多层或动态多层网络）在网络科学中获得更大的相关性，研究在哪种情况下，基于算法信息理论的通用算法方法在哪种情况下，应用于图形上的算法信息理论不能直接地将其直接提高到多维分子中。在这个方向上，作为无损压缩性失真的最坏情况，随着不同尺寸的数量线性增加，本文提出了一种违反直觉现象，当与非均匀且足够大的多维空间打交道时，会发生这种现象。特别是，我们证明了编码具有同构与对数可压缩的单声道网络所必需的算法信息可能在一般情况下显示出指数较大的变形。
Network complexity, network information content analysis, and lossless compressibility of graph representations have been played an important role in network analysis and network modeling. As multidimensional networks, such as time-varying, multilayer, or dynamic multilayer networks, gain more relevancy in network science, it becomes crucial to investigate in which situations universal algorithmic methods based on algorithmic information theory applied to graphs cannot be straightforwardly imported into the multidimensional case. In this direction, as a worst-case scenario of lossless compressibility distortion that increases linearly with the number of distinct dimensions, this article presents a counter-intuitive phenomenon that occurs when dealing with networks within non-uniform and sufficiently large multidimensional spaces. In particular, we demonstrate that the algorithmic information necessary to encode multidimensional networks that are isomorphic to logarithmically compressible monoplex networks may display exponentially larger distortions in the general case.
