On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy
On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy
复制标题
DOI：
10.1155/2017/3250301
复制
发表时间：
2017-01-01
期刊：
影响因子：
2.3
通讯作者：
Kazienko, Przemyslaw
中科院分区：
文献类型：
--
作者：
Morzy, Mikolaj;Kajdanowicz, Tomasz;Kazienko, Przemyslaw
估计网络复杂性的最流行的方法之一是测量网络不变量的熵，例如邻接矩阵或度序列。不幸的是，熵和所有基于熵的信息论测量都有几个漏洞。这些度量既不独立于网络的特定表示，也不能捕获产生网络的生成过程的属性。相反，我们提倡使用算法熵作为网络复杂性定义的基础。算法熵（也称为柯尔莫哥洛夫复杂度或简称 K-复杂度）评估网络无损重建所需的描述的复杂度。该度量不受网络特征的特定选择的影响，并且不依赖于网络表示的方法。我们对逐渐演化的网络的香农熵和 K 复杂度进行了实验。这些实验的结果表明 K 复杂度是网络复杂度更稳健、更可靠的衡量标准。本文的原创贡献包括引入几种新的熵欺骗网络，以及对熵和 K 复杂性作为构建网络复杂性度量的基本量进行实证比较。
One of the most popular methods of estimating the complexity of networks is to measure the entropy of network invariants, such as adjacency matrices or degree sequences. Unfortunately, entropy and all entropy-based information-theoretic measures have several vulnerabilities. These measures neither are independent of a particular representation of the network nor can capture the properties of the generative process, which produces the network. Instead, we advocate the use of the algorithmic entropy as the basis for complexity definition for networks. Algorithmic entropy (also known as Kolmogorov complexity or K-complexity for short) evaluates the complexity of the description required for a lossless recreation of the network. This measure is not affected by a particular choice of network features and it does not depend on the method of network representation. We perform experiments on Shannon entropy and K-complexity for gradually evolving networks. The results of these experiments point to K-complexity as the more robust and reliable measure of network complexity. The original contribution of the paper includes the introduction of several new entropy-deceiving networks and the empirical comparison of entropy and K-complexity as fundamental quantities for constructing complexity measures for networks.