{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T22:22:40Z","timestamp":1762899760163,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T00:00:00Z","timestamp":1559520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["2015-05299"],"award-info":[{"award-number":["2015-05299"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probability that a system will be in a certain state compared to the rest of the elements in the distribution. Because classical entropy-based Maxent collapses cases confounding all distinct degrees of randomness and pseudo-randomness, here we take into consideration the generative mechanism of the systems considered in the ensemble to separate objects that may comply with the principle under some restriction and whose entropy is maximal but may be generated recursively from those that are actually algorithmically random offering a refinement to classical Maxent. We take advantage of a causal algorithmic calculus to derive a thermodynamic-like result based on how difficult it is to reprogram a computer code. Using the distinction between computable and algorithmic randomness, we quantify the cost in information loss associated with reprogramming. To illustrate this, we apply the algorithmic refinement to Maxent on graphs and introduce a Maximal Algorithmic Randomness Preferential Attachment (MARPA) Algorithm, a generalisation over previous approaches. We discuss practical implications of evaluation of network randomness. Our analysis provides insight in that the reprogrammability asymmetry appears to originate from a non-monotonic relationship to algorithmic probability. Our analysis motivates further analysis of the origin and consequences of the aforementioned asymmetries, reprogrammability, and computation.<\/jats:p>","DOI":"10.3390\/e21060560","type":"journal-article","created":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T11:31:01Z","timestamp":1559561461000},"page":"560","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy"],"prefix":"10.3390","volume":"21","author":[{"given":"Hector","family":"Zenil","sequence":"first","affiliation":[{"name":"Algorithmic Dynamics Lab, Karolinska Institute, 17177 Stockholm, Sweden"},{"name":"Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine Solna, Karolinska Institute, 17177 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratory of Scientific Research (LABORES) for the Natural and Digital Sciences, 75006 Paris, France"},{"name":"Oxford Immune Algorithmics, Oxford University Innovation, Reading RG1 7TT, UK"},{"name":"Biological and Environmental Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia"},{"name":"Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0949-046X","authenticated-orcid":false,"given":"Narsis A.","family":"Kiani","sequence":"additional","affiliation":[{"name":"Algorithmic Dynamics Lab, Karolinska Institute, 17177 Stockholm, Sweden"},{"name":"Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine Solna, Karolinska Institute, 17177 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratory of Scientific Research (LABORES) for the Natural and Digital Sciences, 75006 Paris, France"}]},{"given":"Jesper","family":"Tegn\u00e9r","sequence":"additional","affiliation":[{"name":"Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine Solna, Karolinska Institute, 17177 Stockholm, Sweden"},{"name":"Biological and Environmental Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia"},{"name":"Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia"}]}],"member":"1968","published-online":{"date-parts":[[2019,6,3]]},"reference":[{"key":"ref_1","unstructured":"Angrist, S.W., and Helper, L.G. (1967). Order and Chaos. Laws of Energy and Entropy, Basic Books."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1006\/jcss.1999.1677","article-title":"Inequalities for Shannon entropies and Kolmogorov complexities","volume":"60","author":"Hammer","year":"2000","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_3","unstructured":"Gr\u00fcnwald, P., and Vit\u00e1nyi, P. (2004). Shannon Information and Kolmogorov Complexity. arXiv."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1007\/BF01341281","article-title":"On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings","volume":"53","author":"Szilard","year":"1929","journal-title":"Z. Phys."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0003-4916(88)90094-2","article-title":"Complexity as thermodynamic depth","volume":"188","author":"Lloyd","year":"1988","journal-title":"Ann. Phys."},{"key":"ref_6","unstructured":"Herken, R. (1988). Logical Depth and Physical Complexity. The Universal Turing Machine: A Half-Century Survey, Oxford University Press."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1017\/S0960129511000521","article-title":"Algorithmic Thermodynamics, Computability of the Physical","volume":"22","author":"Baez","year":"2012","journal-title":"Math. Struct. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1103\/PhysRevE.59.275","article-title":"Thermodynamic depth of causal states: Objective complexity via minimal representations","volume":"59","author":"Crutchfield","year":"1999","journal-title":"Phys. Rev. E"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"4731","DOI":"10.1103\/PhysRevA.40.4731","article-title":"Algorithmic randomness and physical entropy","volume":"40","author":"Zurek","year":"1989","journal-title":"Phys. Rev. A"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1038\/341119a0","article-title":"Thermodynamic cost of computation, algorithmic complexity, and the information metric","volume":"341","author":"Zurek","year":"1989","journal-title":"Nature"},{"key":"ref_11","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Probl. Inf. Transm."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/S0019-9958(64)90131-7","article-title":"A formal theory of inductive inference: Parts 1 and 2","volume":"7","author":"Solomonoff","year":"1964","journal-title":"Inf. Control"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","article-title":"On the length of programs for computing finite binary sequences","volume":"13","author":"Chaitin","year":"1966","journal-title":"J. ACM"},{"key":"ref_14","first-page":"206","article-title":"Laws of information conservation (non-growth) and aspects of the foundation of probability theory","volume":"10","author":"Levin","year":"1974","journal-title":"Probl. Inf. Transm."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"012308","DOI":"10.1103\/PhysRevE.96.012308","article-title":"Low Algorithmic Complexity Entropy-deceiving Graphs","volume":"96","author":"Zenil","year":"2017","journal-title":"Phys. Rev. E"},{"key":"ref_16","first-page":"290","article-title":"On Random Graphs I","volume":"6","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"ref_17","first-page":"343","article-title":"On the evolution of random graphs","volume":"38","year":"1961","journal-title":"Bull. Inst. Int. Stat"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random graphs","volume":"30","author":"Gilbert","year":"1959","journal-title":"Ann. Math. Stat."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Adamatzky, A. (2019). Algorithmic Information Dynamics of Emergent, Persistent, and Colliding Particles in the Game of Life. From Parallel to Emergent Computing, Taylor & Francis\/CRC Press.","DOI":"10.1201\/9781315167084"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1038\/s42256-018-0005-0","article-title":"Causal Deconvolution by Algorithmic Generative Models","volume":"1","author":"Zenil","year":"2019","journal-title":"Nat. Mach. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2014.07.001","article-title":"The structure and dynamics of multilayer networks","volume":"544","author":"Boccaletti","year":"2014","journal-title":"Phys. Rep."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1016\/j.amc.2014.05.105","article-title":"Entropy bounds for dendrimers","volume":"24","author":"Chen","year":"2014","journal-title":"Appl. Math. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"8627","DOI":"10.1038\/ncomms9627","article-title":"Quantifying randomness in real networks","volume":"6","author":"Orsini","year":"2015","journal-title":"Nat. Commun."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1109\/18.2639","article-title":"Random access communication and graph entropy","volume":"34","author":"Korner","year":"1988","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.laa.2013.11.009","article-title":"Walk entropies in graphs","volume":"443","author":"Estrada","year":"2014","journal-title":"Linear Algebra Appl."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ins.2010.08.041","article-title":"A history of graph entropy measures","volume":"181","author":"Dehmer","year":"2011","journal-title":"Inf. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"595","DOI":"10.3390\/e13030595","article-title":"Entropy Measures vs. Kolmogorov Complexity","volume":"13","author":"Teixeira","year":"2011","journal-title":"Entropy"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1093\/comnet\/cnv025","article-title":"Quantifying loss of information in network-based dimensionality reduction techniques","volume":"4","author":"Zenil","year":"2016","journal-title":"J. Complex Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/j.physa.2014.02.060","article-title":"Graph Automorphisms and Topological Characterization of Complex Networks by Algorithmic Information Content","volume":"404","author":"Zenil","year":"2014","journal-title":"Physica A"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., and Tegn\u00e9r, J. (2013, January 18\u201321). Algorithmic complexity of motifs clusters superfamilies of networks. Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine, Shanghai, China.","DOI":"10.1109\/BIBM.2013.6732768"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF03024407","article-title":"The miraculous universal distribution","volume":"19","author":"Kirchherr","year":"1997","journal-title":"J. Math. Intell."},{"key":"ref_32","unstructured":"Calude, C.S. (2010). Information and Randomness: An Algorithmic Perspective, Springer. [2nd ed.]."},{"key":"ref_33","unstructured":"Cover, T.M., and Thomas, J.A. (2009). Elements of Information Theory, Wiley-Blackwell. [2nd ed.]."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1137\/S0097539797327805","article-title":"Kolmogorov Random Graphs and the Incompressibility Method","volume":"29","author":"Buhrman","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.amc.2011.10.006","article-title":"Numerical Evaluation of the Complexity of Short Strings: A Glance Into the Innermost Structure of Algorithmic Randomness","volume":"219","author":"Delahaye","year":"2012","journal-title":"Appl. Math. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Soler-Toscano, F., Zenil, H., Delahaye, J.-P., and Gauvrit, N. (2014). Calculating Kolmogorov Complexity from the Frequency Output Distributions of Small Turing Machines. PLoS ONE, 9.","DOI":"10.1371\/journal.pone.0096223"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Zenil, H., Soler-Toscano, F., Kiani, N.A., Hern\u00e1ndez-Orozco, S., and Rueda-Toicen, A. (2018). A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity. Entropy, 20.","DOI":"10.3390\/e20080605"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., Marabita, F., Deng, Y., Elias, S., Schmidt, A., Ball, G., and Tegn\u00e9r, J. (2018). An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems. bioRxiv, 185637.","DOI":"10.2139\/ssrn.3193409"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Zenil, H., Soler-Toscano, F., Delahaye, J.-P., and Gauvrit, N. (2015). Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility. PeerJ Comput. Sci.","DOI":"10.7717\/peerj-cs.23"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.semcdb.2016.01.011","article-title":"Methods of Information Theory and Algorithmic Complexity for Network Biology","volume":"51","author":"Zenil","year":"2016","journal-title":"Semin. Cell Dev. Biol."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"28005","DOI":"10.1209\/0295-5075\/81\/28005","article-title":"The entropy of randomized network ensembles","volume":"81","author":"Bianconi","year":"2007","journal-title":"EPL (Europhys. Lett.)"},{"key":"ref_42","unstructured":"Zenil, H., Kiani, N.A., and Tegn\u00e9r, J. (2018). Minimal Algorithmic Information Loss Methods for Dimension Reduction, Feature Selection and Network Sparsification. arXiv."},{"key":"ref_43","unstructured":"Zenil, H., Badillo, L., Hern\u00e1ndez-Orozco, S., and Hern\u00e1ndez-Quiroz, F. (2018). Coding-theorem Like Behaviour and Emergence of the Universal Distribution from Resource-bounded Algorithmic Probability. Int. J. Parallel Emerg. Distrib. Syst."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF01594179","article-title":"Die Widerspruchsfreiheit der allgemeinen Mengenlehre","volume":"114","author":"Ackermann","year":"1937","journal-title":"Math. Ann."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"331","DOI":"10.4064\/aa-9-4-331-340","article-title":"Universal graphs and universal functions","volume":"9","author":"Rado","year":"1964","journal-title":"Acta Arith."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Gauvrit, N., Zenil, H., Soler-Toscano, F., Delahaye, J.-P., and Brugger, P. (2017). Human Behavioral Complexity Peaks at Age 25. PLoS Comput. Biol., 13.","DOI":"10.1371\/journal.pcbi.1005408"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Soler-Toscano, F., and Zenil, H. (2017). A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences. Complexity, 2017.","DOI":"10.1155\/2017\/7208216"},{"key":"ref_48","unstructured":"Ott, M., Pietsch, W., and Wernecke, J. (2017). Algorithmic Data Analytics, Small Data Matters and Correlation versus Causation. Berechenbarkeit der Welt? Philosophie und Wissenschaft im Zeitalter von Big Data (Computability of the World? Philosophy and Science in the Age of Big Data), Springer."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., and Tegn\u00e9r, J. (2018). A Review of Graph and Network Complexity from an Algorithmic Information Perspective. Entropy, 20.","DOI":"10.3390\/e20080551"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/6\/560\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:55:52Z","timestamp":1760187352000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/6\/560"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,3]]},"references-count":49,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["e21060560"],"URL":"https:\/\/doi.org\/10.3390\/e21060560","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2019,6,3]]}}}