On measuring the complexity of networks: Kolmogorov complexity versus entropy
type: Item
instance of: scholarly article
title: On measuring the complexity of networks: Kolmogorov complexity versus entropy
zbMATH Open document ID: 1378.90034
DOI: 10.1155/2017/3250301
author: Mikołaj Morzy
author: Tomasz Kajdanowicz
author: Przemysław Kazienko
published in: Complexity
publication date: 2018-01-03T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 94A17
zbMATH DE Number: 6821574
zbMATH Keywords: complexity of networks
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: entropy of network invariants
zbMATH Keywords: lossless recreation of networks
zbMATH Keywords: Shannon entropy
zbMATH Keywords: robust and reliable measure of network complexity
describes a project that uses: acss
describes a project that uses: OACC
describes a project that uses: OEIS
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2017/3250301
OpenAlex ID: W2765310599
Wikidata QID: Q60692609
cites work: Q5485943
cites work: Graph complexity and the laplacian matrix in blocked experiments
cites work: The linear complexity of a graph
cites work: Mathematical Foundations and Applications of Graph Entropy
cites work: A history of graph entropy measures
cites work: Entropy and the complexity of graphs revisited
cites work: Extremality of degree-based graph entropies
cites work: A note on distance-based graph entropies
cites work: Q2975321
cites work: Laplacian energy of a graph
cites work: Q5801644
cites work: Three approaches to the quantitative definition of information*
cites work: Q3292859
cites work: Entropy and the complexity of graphs: I. An index of the relative complexity of a graph
cites work: Information processing in complex networks: Graph entropy and information functionals
cites work: Network entropies based on independent sets and matchings
cites work: Fredman–Komlós bounds and information theory
cites work: Q4443440
cites work: On the Length of Programs for Computing Finite Binary Sequences
cites work: Q4070739
cites work: A formal theory of inductive inference. Part I
cites work: On Non-Computable Functions
cites work: Collective dynamics of ‘small-world’ networks
cites work: Q3286850
cites work: Emergence of Scaling in Random Networks
cites work: Scale-Free Networks: A Decade and Beyond
cites work: The Structure and Function of Complex Networks
cites work: Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
description: scientific article; zbMATH DE number 6821574