{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:22:46Z","timestamp":1772252566934,"version":"3.50.1"},"reference-count":30,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["301.322\/2020-1"],"award-info":[{"award-number":["301.322\/2020-1"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["303.193\/2020-4"],"award-info":[{"award-number":["303.193\/2020-4"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["310.201\/2019-5"],"award-info":[{"award-number":["310.201\/2019-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Instituto Nacional de Ci\u00eancia e Tecnologia em Ci\u00eancia de Dados","award":["465.560\/2014-8"],"award-info":[{"award-number":["465.560\/2014-8"]}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["e-26\/203.046\/2017"],"award-info":[{"award-number":["e-26\/203.046\/2017"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this article, we investigate limitations of importing methods based on algorithmic information theory from monoplex networks into multidimensional networks (such as multilayer networks) that have a large number of extra dimensions (i.e., aspects). In the worst-case scenario, it has been previously shown that node-aligned multidimensional networks with non-uniform multidimensional spaces can display exponentially larger algorithmic information (or lossless compressibility) distortions with respect to their isomorphic monoplex networks, so that these distortions grow at least linearly with the number of extra dimensions. In the present article, we demonstrate that node-unaligned multidimensional networks, either with uniform or non-uniform multidimensional spaces, can also display exponentially larger algorithmic information distortions with respect to their isomorphic monoplex networks. However, unlike the node-aligned non-uniform case studied in previous work, these distortions in the node-unaligned case grow at least exponentially with the number of extra dimensions. On the other hand, for node-aligned multidimensional networks with uniform multidimensional spaces, we demonstrate that any distortion can only grow up to a logarithmic order of the number of extra dimensions. Thus, these results establish that isomorphisms between finite multidimensional networks and finite monoplex networks do not preserve algorithmic information in general and highlight that the algorithmic information of the multidimensional space itself needs to be taken into account in multidimensional network complexity analysis.<\/jats:p>","DOI":"10.3390\/e23070835","type":"journal-article","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T22:39:43Z","timestamp":1625006383000},"page":"835","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7314-6543","authenticated-orcid":false,"given":"Felipe S.","family":"Abrah\u00e3o","sequence":"first","affiliation":[{"name":"National Laboratory for Scientific Computing (LNCC), Petropolis 25651-075, RJ, Brazil"},{"name":"Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, Algorithmic Nature Group, 75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2694-3931","authenticated-orcid":false,"given":"Klaus","family":"Wehmuth","sequence":"additional","affiliation":[{"name":"National Laboratory for Scientific Computing (LNCC), Petropolis 25651-075, RJ, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0634-4384","authenticated-orcid":false,"given":"Hector","family":"Zenil","sequence":"additional","affiliation":[{"name":"Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, Algorithmic Nature Group, 75005 Paris, France"},{"name":"British Library, The Alan Turing Institute, 2QR, 96 Euston Rd, London NW1 2DB, UK"},{"name":"Oxford Immune Algorithmics, Reading RG1 3EU, UK"},{"name":"Center for Molecular Medicine, Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Karolinska Institute, SE-171 77 Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9326-8214","authenticated-orcid":false,"given":"Artur","family":"Ziviani","sequence":"additional","affiliation":[{"name":"National Laboratory for Scientific Computing (LNCC), Petropolis 25651-075, RJ, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Chaitin, G. (2004). Algorithmic Information Theory, Cambridge University Press. [3rd ed.].","DOI":"10.1002\/0471667196.ess0029"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Li, M., and Vit\u00e1nyi, P. (2019). An Introduction to Kolmogorov Complexity and Its Applications, Springer. [4th ed.].","DOI":"10.1007\/978-3-030-11298-1"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Calude, C.S. (2002). Information and Randomness: An Algorithmic Perspective, Springer. [2nd ed.].","DOI":"10.1007\/978-3-662-04978-5"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Hirschfeldt, D.R. (2010). Algorithmic Randomness and Complexity, Springer. Theory and Applications of Computability.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"559","DOI":"10.3390\/e14030559","article-title":"Entropy and the complexity of graphs revisited","volume":"14","author":"Mowshowitz","year":"2012","journal-title":"Entropy"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Morzy, M., Kajdanowicz, T., and Kazienko, P. (2017). On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy. Complexity, 2017.","DOI":"10.1155\/2017\/3250301"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N., and Tegn\u00e9r, J. (2018). A Review of Graph and Network Complexity from an Algorithmic Information Perspective. Entropy, 20.","DOI":"10.3390\/e20080551"},{"key":"ref_8","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_9","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., Abrah\u00e3o, F.S., Rueda-Toicen, A., Zea, A.A., and Tegn\u00e9r, J. (2020). Minimal Algorithmic Information Loss Methods for Dimension Reduction, Feature Selection and Network Sparsification. arXiv.","DOI":"10.4249\/scholarpedia.53143"},{"key":"ref_10","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_11","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/j.physa.2014.02.060","article-title":"Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks","volume":"404","author":"Zenil","year":"2014","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"ref_12","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_13","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., and Tegn\u00e9r, J. (2019). The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy. Entropy, 21.","DOI":"10.3390\/e21060560"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Santoro, A., and Nicosia, V. (2020). Algorithmic Complexity of Multiplex Networks. Phys. Rev. X, 10.","DOI":"10.1103\/PhysRevX.10.021069"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1007\/978-3-030-65351-4_42","article-title":"An Algorithmic Information Distortion in Multidimensional Networks","volume":"Volume 944","author":"Benito","year":"2021","journal-title":"Complex Networks & Their Applications IX"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Abrah\u00e3o, F.S., Wehmuth, K., Zenil, H., and Ziviani, A. (2021). Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks. Preprints.","DOI":"10.20944\/preprints202103.0056.v1"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.tcs.2016.08.017","article-title":"On MultiAspect graphs","volume":"651","author":"Wehmuth","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Wehmuth, K., Fleury, \u00c9., and Ziviani, A. (2017). MultiAspect Graphs: Algebraic Representation and Algorithms. Algorithms, 10.","DOI":"10.3390\/a10010001"},{"key":"ref_19","unstructured":"Abrah\u00e3o, F.S., Wehmuth, K., Zenil, H., and Ziviani, A. (2018). On incompressible multidimensional networks. arXiv."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (1998). Modern Graph Theory, Springer.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2017). Graph Theory, Springer. [5th ed.].","DOI":"10.1007\/978-3-662-53622-3"},{"key":"ref_22","unstructured":"Harary, F. (2018). Graph Theory, CRC Press."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Newman, M. (2010). Networks: An Introduction, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199206650.003.0001"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1093\/comnet\/cnu016","article-title":"Multilayer networks","volume":"2","author":"Kivela","year":"2014","journal-title":"J. Complex Netw."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cozzo, E., de Arruda, G.F., Rodrigues, F.A., and Moreno, Y. (2018). Multiplex Networks, Springer International Publishing. SpringerBriefs in Complexity.","DOI":"10.1007\/978-3-319-92255-3"},{"key":"ref_26","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_27","doi-asserted-by":"crossref","unstructured":"De Domenico, M., Sol\u00e9-Ribalta, A., Cozzo, E., Kivel\u00e4, M., Moreno, Y., Porter, M.A., G\u00f3mez, S., and Arenas, A. (2013). Mathematical Formulation of Multilayer Networks. Phys. Rev. X, 3.","DOI":"10.1103\/PhysRevX.3.041022"},{"key":"ref_28","unstructured":"Calude, C.S. (1994). Borel Normality and Algorithmic Randomness. Developments in Language Theory, World Scientific Publishing."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., and Tegn\u00e9r, J. (2017). Low-Algorithmic-Complexity Entropy-Deceiving Graphs. Phys. Rev. E, 96.","DOI":"10.1103\/PhysRevE.96.012308"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/S0304-3975(01)00170-0","article-title":"An Example of a Computable Absolutely Normal Number","volume":"270","author":"Becher","year":"2002","journal-title":"Theor. Comput. Sci."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/7\/835\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:27:22Z","timestamp":1760164042000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/7\/835"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,29]]},"references-count":30,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2021,7]]}},"alternative-id":["e23070835"],"URL":"https:\/\/doi.org\/10.3390\/e23070835","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202103.0056.v2","asserted-by":"object"},{"id-type":"doi","id":"10.20944\/preprints202103.0056.v1","asserted-by":"object"}]},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,29]]}}}