{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T08:03:12Z","timestamp":1742803392728,"version":"3.37.3"},"reference-count":43,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2018,7,25]],"date-time":"2018-07-25T00:00:00Z","timestamp":1532476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon\u2019s entropy, lossless compressibility and algorithmic complexity when used to identify aspects and properties of complex networks. We review the fragility of computable measures on the one hand and the invariant properties of algorithmic measures on the other demonstrating how current approaches to algorithmic complexity are misguided and suffer of similar limitations than traditional statistical approaches such as Shannon entropy. Finally, we review some current definitions of algorithmic complexity which are used in analyzing labelled and unlabelled graphs. This analysis opens up several new opportunities to advance beyond traditional measures.<\/jats:p>","DOI":"10.3390\/e20080551","type":"journal-article","created":{"date-parts":[[2018,7,25]],"date-time":"2018-07-25T12:28:47Z","timestamp":1532521727000},"page":"551","source":"Crossref","is-referenced-by-count":58,"title":["A Review of Graph and Network Complexity from an Algorithmic Information Perspective"],"prefix":"10.3390","volume":"20","author":[{"given":"Hector","family":"Zenil","sequence":"first","affiliation":[{"name":"Algorithmic Dynamics Lab, Centre for Molecular Medicine, Karolinska Institute, 171 77 Stockholm, Sweden"},{"name":"Unit of Computational Medicine, Department of Medicine, Karolinska Institute, 171 77 Stockholm, Sweden"},{"name":"Science for Life Laboratory (SciLifeLab), 171 77 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France"},{"name":"Biological and Environmental Sciences and Engineering Division (BESE), 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, Centre for Molecular Medicine, Karolinska Institute, 171 77 Stockholm, Sweden"},{"name":"Unit of Computational Medicine, Department of Medicine, Karolinska Institute, 171 77 Stockholm, Sweden"},{"name":"Science for Life Laboratory (SciLifeLab), 171 77 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France"}]},{"given":"Jesper","family":"Tegn\u00e9r","sequence":"additional","affiliation":[{"name":"Unit of Computational Medicine, Department of Medicine, Karolinska Institute, 171 77 Stockholm, Sweden"},{"name":"Science for Life Laboratory (SciLifeLab), 171 77 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France"},{"name":"Biological and Environmental Sciences and Engineering Division (BESE), King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia"}]}],"member":"1968","published-online":{"date-parts":[[2018,7,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zenil, H., Badillo, L., Hern\u00e1ndez-Orozco, S., and Hernandez-Quiroz, F. (2018). Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability. Int. J. Parallel Emergent Distrib. Syst.","DOI":"10.1080\/17445760.2018.1448932"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Pietsch, W., Wernecke, J., and Ott, M. (2017). Small data matters, correlation versus causation and algorithmic data analytics. Berechenbarkeit der Welt?, Springer.","DOI":"10.1007\/978-3-658-12153-2"},{"key":"ref_4","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":"Phys. A Stat. Mech. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Babai, L., and Luks, E.M. (1983, January 25\u201327). Canonical labelling of graphs. Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, USA.","DOI":"10.1145\/800061.808746"},{"key":"ref_6","first-page":"290","article-title":"On random graphs I","volume":"6","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"ref_7","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_8","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_9","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1016\/j.amc.2014.05.105","article-title":"Entropy bounds for dendrimers","volume":"242","author":"Chen","year":"2014","journal-title":"Appl. Math. Comput."},{"key":"ref_10","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_11","unstructured":"Zenil, H., Kiani, N.A., and Tegn\u00e9r, J. (arXiv, 2018). An algorithmic refinement of maxent induces a thermodynamic-like behaviour in the reprogrammability of generative mechanisms, arXiv."},{"key":"ref_12","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"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Shang, Y. (2016). Bounding extremal degrees of edge-independent random graphs using relative entropy. Entropy, 18.","DOI":"10.3390\/e18020053"},{"key":"ref_14","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_15","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_16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.4236\/cmb.2016.63004","article-title":"Application of graph entropy in CRISPR and repeats detection in DNA sequences","volume":"6","author":"Sengupta","year":"2016","journal-title":"Comput. Mol. Biosci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/j.amc.2014.10.129","article-title":"The Estrada index of evolving graphs","volume":"250","author":"Shang","year":"2015","journal-title":"Appl. Math. Comput."},{"key":"ref_18","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_19","doi-asserted-by":"crossref","unstructured":"Dehmer, M., Borgert, S., and Emmert-Streib, F. (2008). Entropy bounds for hierarchical molecular networks. PLoS ONE, 3.","DOI":"10.1371\/journal.pone.0003079"},{"key":"ref_20","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":"Phy. Rev. E"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"3250301","DOI":"10.1155\/2017\/3250301","article-title":"On measuring the complexity of networks: Kolmogorov complexity versus entropy","volume":"2017","author":"Morzy","year":"2017","journal-title":"Complexity"},{"key":"ref_22","unstructured":"Zenil, H., Soler-Toscano, F., Kiani, N.A., Hern\u00e1ndez-Orozco, S., and Rueda-Toicen, A. (arXiv, 2016). A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity, arXiv."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1080\/00207166808803030","article-title":"Three approaches to the quantitative definition of information","volume":"2","author":"Kolmogorov","year":"1968","journal-title":"Int. J. Comput. Math."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","article-title":"The definition of random sequences","volume":"9","year":"1966","journal-title":"Inform. Contr."},{"key":"ref_25","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_26","first-page":"224","article-title":"A formal theory of inductive inference: Parts 1 and 2","volume":"13","author":"Solomonoff","year":"1964","journal-title":"Inf. Comput."},{"key":"ref_27","first-page":"30","article-title":"Laws of information conservation (non-growth) and aspects of the foundation of probability theory","volume":"210","author":"Levin","year":"1974","journal-title":"Probl. Inform. Trans."},{"key":"ref_28","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_29","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":"2015","journal-title":"J. Complex Netw."},{"key":"ref_30","unstructured":"Calude, C.S. (2013). Information and Randomness: An Algorithmic Perspective, Springer. [2nd ed.]."},{"key":"ref_31","unstructured":"Li, M., and Vit\u00e1nyi, P. (2009). An Introduction to Kolmogorov Complexity and Its Applications, Springer. [3rd ed.]."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","article-title":"On computable numbers, with an application to the entscheidungsproblem","volume":"2","author":"Turing","year":"1937","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_33","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":"Math. Intell."},{"key":"ref_34","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley & Sons. [2nd ed.]."},{"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","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_38","doi-asserted-by":"crossref","first-page":"e23","DOI":"10.7717\/peerj-cs.23","article-title":"Two-dimensional kolmogorov complexity and validation of the coding theorem method by compressibility","volume":"1","author":"Zenil","year":"2015","journal-title":"PeerJ Comput. Sci."},{"key":"ref_39","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_40","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1038\/nrg2102","article-title":"Network motifs: Theory and experimental approaches","volume":"450","author":"Alon","year":"2007","journal-title":"Nat. Rev. Genet."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/0167-2789(86)90237-X","article-title":"Studying artificial life with cellular automata","volume":"22","author":"Langton","year":"1986","journal-title":"Phys. D Nonlinear Phenom."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: Simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., Marabita, F., Deng, Y., Elias, S., Schmidt, A., Ball, G., and Tegn\u00e9r, J. (2017). An algorithmic information calculus for causal discovery and reprogramming systems. bioarXiv.","DOI":"10.1101\/185637"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/8\/551\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T21:32:15Z","timestamp":1718141535000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/8\/551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,25]]},"references-count":43,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2018,8]]}},"alternative-id":["e20080551"],"URL":"https:\/\/doi.org\/10.3390\/e20080551","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2018,7,25]]}}}