Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks
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 previousl...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-06-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/23/7/835 |
| _version_ | 1797528368143400960 |
|---|---|
| author | Felipe S. Abrahão Klaus Wehmuth Hector Zenil Artur Ziviani |
| author_facet | Felipe S. Abrahão Klaus Wehmuth Hector Zenil Artur Ziviani |
| author_sort | Felipe S. Abrahão |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T09:57:16Z |
| format | Article |
| id | doaj.art-fb76aac056ba410ea270af761935e440 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T09:57:16Z |
| publishDate | 2021-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-fb76aac056ba410ea270af761935e4402023-11-22T02:17:35ZengMDPI AGEntropy1099-43002021-06-0123783510.3390/e23070835Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional NetworksFelipe S. Abrahão0Klaus Wehmuth1Hector Zenil2Artur Ziviani3National Laboratory for Scientific Computing (LNCC), Petropolis 25651-075, RJ, BrazilNational Laboratory for Scientific Computing (LNCC), Petropolis 25651-075, RJ, BrazilLaboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, Algorithmic Nature Group, 75005 Paris, FranceNational Laboratory for Scientific Computing (LNCC), Petropolis 25651-075, RJ, BrazilIn 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.https://www.mdpi.com/1099-4300/23/7/835multidimensional networksnetwork complexitylossless compressioninformation distortiongraph isomorphismmultiaspect graphs |
| spellingShingle | Felipe S. Abrahão Klaus Wehmuth Hector Zenil Artur Ziviani Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks Entropy multidimensional networks network complexity lossless compression information distortion graph isomorphism multiaspect graphs |
| title | Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks |
| title_full | Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks |
| title_fullStr | Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks |
| title_full_unstemmed | Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks |
| title_short | Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks |
| title_sort | algorithmic information distortions in node aligned and node unaligned multidimensional networks |
| topic | multidimensional networks network complexity lossless compression information distortion graph isomorphism multiaspect graphs |
| url | https://www.mdpi.com/1099-4300/23/7/835 |
| work_keys_str_mv | AT felipesabrahao algorithmicinformationdistortionsinnodealignedandnodeunalignedmultidimensionalnetworks AT klauswehmuth algorithmicinformationdistortionsinnodealignedandnodeunalignedmultidimensionalnetworks AT hectorzenil algorithmicinformationdistortionsinnodealignedandnodeunalignedmultidimensionalnetworks AT arturziviani algorithmicinformationdistortionsinnodealignedandnodeunalignedmultidimensionalnetworks |