Initiative for the Theoretical Sciences, Graduate Center, City University of New York, New York, NY 10016.
Joseph Henry Laboratories of Physics, Princeton University, Princeton, NJ 08544.
Proc Natl Acad Sci U S A. 2021 Aug 10;118(32). doi: 10.1073/pnas.2023473118.
Many complex networks depend upon biological entities for their preservation. Such entities, from human cognition to evolution, must first encode and then replicate those networks under marked resource constraints. Networks that survive are those that are amenable to constrained encoding-or, in other words, are compressible. But how compressible is a network? And what features make one network more compressible than another? Here, we answer these questions by modeling networks as information sources before compressing them using rate-distortion theory. Each network yields a unique rate-distortion curve, which specifies the minimal amount of information that remains at a given scale of description. A natural definition then emerges for the compressibility of a network: the amount of information that can be removed via compression, averaged across all scales. Analyzing an array of real and model networks, we demonstrate that compressibility increases with two common network properties: transitivity (or clustering) and degree heterogeneity. These results indicate that hierarchical organization-which is characterized by modular structure and heterogeneous degrees-facilitates compression in complex networks. Generally, our framework sheds light on the interplay between a network's structure and its capacity to be compressed, enabling investigations into the role of compression in shaping real-world networks.
许多复杂网络依赖于生物实体来维持其存在。从人类认知到进化，这些实体必须首先对这些网络进行编码，然后在显著的资源限制下进行复制。能够幸存下来的网络是那些易于受限编码的网络，换句话说，就是可压缩的。但是，网络的可压缩性如何？哪些特征使得一个网络比另一个网络更具可压缩性？在这里，我们通过在使用率失真理论压缩网络之前将网络建模为信息源来回答这些问题。每个网络都会产生一个独特的率失真曲线，该曲线指定了在给定描述尺度下保留的最小信息量。然后，就会出现一个网络可压缩性的自然定义：通过压缩可以去除的信息量，在所有尺度上平均。通过分析一系列真实和模型网络，我们证明了可压缩性随着两个常见的网络属性而增加：传递性（或聚类）和度异质性。这些结果表明，层次组织——其特征是模块化结构和异质度——促进了复杂网络中的压缩。通常，我们的框架揭示了网络结构与其可压缩性之间的相互作用，使我们能够研究压缩在塑造现实世界网络中的作用。
