TY - JOUR

T1 - Low-algorithmic-complexity entropy-deceiving graphs

AU - Zenil, Hector

AU - Kiani, Narsis A.

AU - Tegner, Jesper

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: N.A.K. was supported by aVinnovaVINNMERfellowship, Stratneuro. H. Z. was supported by the Swedish Research Council (VR).

PY - 2017/7/7

Y1 - 2017/7/7

N2 - In estimating the complexity of objects, in particular, of graphs, it is common practice to rely on graphand information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which an object, such as a graph, can be described or observed. From observations that can reconstruct the same graph and are therefore essentially translations of the same description, we see that when applying a computable measure such as the Shannon entropy, not only is it necessary to preselect a feature of interest where there is one, and to make an arbitrary selection where there is not, but also more general properties, such as the causal likelihood of a graph as a measure (opposed to randomness), can be largely misrepresented by computable measures such as the entropy and entropy rate. We introduce recursive and nonrecursive (uncomputable) graphs and graph constructions based on these integer sequences, whose different lossless descriptions have disparate entropy values, thereby enabling the study and exploration of a measure's range of applications and demonstrating the weaknesses of computable measures of complexity.

AB - In estimating the complexity of objects, in particular, of graphs, it is common practice to rely on graphand information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which an object, such as a graph, can be described or observed. From observations that can reconstruct the same graph and are therefore essentially translations of the same description, we see that when applying a computable measure such as the Shannon entropy, not only is it necessary to preselect a feature of interest where there is one, and to make an arbitrary selection where there is not, but also more general properties, such as the causal likelihood of a graph as a measure (opposed to randomness), can be largely misrepresented by computable measures such as the entropy and entropy rate. We introduce recursive and nonrecursive (uncomputable) graphs and graph constructions based on these integer sequences, whose different lossless descriptions have disparate entropy values, thereby enabling the study and exploration of a measure's range of applications and demonstrating the weaknesses of computable measures of complexity.

UR - http://hdl.handle.net/10754/625386

UR - https://journals.aps.org/pre/abstract/10.1103/PhysRevE.96.012308

UR - http://www.scopus.com/inward/record.url?scp=85022344976&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.96.012308

DO - 10.1103/PhysRevE.96.012308

M3 - Article

C2 - 29347130

SN - 2470-0045

VL - 96

JO - Physical Review E

JF - Physical Review E

IS - 1

ER -