On measuring the complexity of networks: Kolmogorov complexity versus entropy

DOI10.1155/2017/3250301zbMath1378.90034OpenAlexW2765310599WikidataQ60692609 ScholiaQ60692609MaRDI QIDQ1687410

Przemysław Kazienko, Tomasz Kajdanowicz, Mikołaj Morzy

Publication date: 3 January 2018

Published in: Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1155/2017/3250301

zbMATH Keywords

Kolmogorov complexityShannon entropycomplexity of networksentropy of network invariantslossless recreation of networksrobust and reliable measure of network complexity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Measures of information, entropy (94A17)

Related Items (5)

On graph entropy measures based on the number of independent sets and matchings ⋮ Detecting causal relations in time series with the new cross Markov matrix technique ⋮ Possibility of recovering message segments based on side information about original characters ⋮ Unnamed Item ⋮ A note on distance-based entropy of dendrimers

Uses Software

• OEIS
• OACC
• acss

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Entropy and the complexity of graphs revisited
• Extremality of degree-based graph entropies
• A history of graph entropy measures
• The linear complexity of a graph
• Laplacian energy of a graph
• Information processing in complex networks: Graph entropy and information functionals
• Network entropies based on independent sets and matchings
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• A note on distance-based graph entropies
• Mathematical Foundations and Applications of Graph Entropy
• Emergence of Scaling in Random Networks
• Scale-Free Networks: A Decade and Beyond
• Graph complexity and the laplacian matrix in blocked experiments
• Fredman–Komlós bounds and information theory
• The Structure and Function of Complex Networks
• On Non-Computable Functions
• Collective dynamics of ‘small-world’ networks
• On the Length of Programs for Computing Finite Binary Sequences
• Entropy and the complexity of graphs: I. An index of the relative complexity of a graph
• Three approaches to the quantitative definition of information^*
• A formal theory of inductive inference. Part I

This page was built for publication: On measuring the complexity of networks: Kolmogorov complexity versus entropy