2014/01/15 by Héctor Zenil, Narsis A. Kiani, Zenil, Hector +3 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Computational Drug Discovery Methods #FOS: Biological sciences #Molecular Networks (q-bio.MN) #Quantitative Methods (q-bio.QM)
paper · pdf · doi:10.48550/arxiv.1401.3604
openalex publication_date 2014/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We survey and introduce concepts and tools located at the intersection of\ninformation theory and network biology. We show that Shannon's information\nentropy, compressibility and algorithmic complexity quantify different local\nand global aspects of synthetic and biological data. We show examples such as\nthe emergence of giant components in Erdos-Renyi random graphs, and the\nrecovery of topological properties from numerical kinetic properties simulating\ngene expression data. We provide exact theoretical calculations, numerical\napproximations and error estimations of entropy, algorithmic probability and\nKolmogorov complexity for different types of graphs, characterizing their\nvariant and invariant properties. We introduce formal definitions of complexity\nfor both labeled and unlabeled graphs and prove that the Kolmogorov complexity\nof a labeled graph is a good approximation of its unlabeled Kolmogorov\ncomplexity and thus a robust definition of graph complexity.\n