Algorithmic Complexity of Multiplex Networks

Multilayer networks preserve full information about the different interactions among the constituents of a complex system, and have recently proven quite useful in modeling transportation networks, social circles, and the human brain. A fundamental and still open problem is to assess if and when the...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Andrea Santoro, Vincenzo Nicosia
Formato:	article
Lenguaje:	EN
Publicado:	American Physical Society 2020
Materias:	Physics QC1-999
Acceso en línea:	https://doaj.org/article/4c65c4f23944489bb51018a5bfef0812
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:4c65c4f23944489bb51018a5bfef0812
record_format	dspace
spelling	oai:doaj.org-article:4c65c4f23944489bb51018a5bfef08122021-12-02T11:37:00ZAlgorithmic Complexity of Multiplex Networks10.1103/PhysRevX.10.0210692160-3308https://doaj.org/article/4c65c4f23944489bb51018a5bfef08122020-06-01T00:00:00Zhttp://doi.org/10.1103/PhysRevX.10.021069http://doi.org/10.1103/PhysRevX.10.021069https://doaj.org/toc/2160-3308Multilayer networks preserve full information about the different interactions among the constituents of a complex system, and have recently proven quite useful in modeling transportation networks, social circles, and the human brain. A fundamental and still open problem is to assess if and when the multilayer representation of a system provides a qualitatively better model than the classical single-layer aggregated network. Here we tackle this problem from an algorithmic information theory perspective. We propose an intuitive way to encode a multilayer network into a bit string, and we define the complexity of a multilayer network as the ratio of the Kolmogorov complexity of the bit strings associated to the multilayer and to the corresponding aggregated graph. We find that there exists a maximum amount of additional information that a multilayer model can encode with respect to the equivalent single-layer graph. We show how our complexity measure can be used to obtain low-dimensional representations of multidimensional systems, to cluster multilayer networks into a small set of meaningful superfamilies, and to detect tipping points in the evolution of different time-varying multilayer graphs. Interestingly, the low-dimensional multiplex networks obtained with the proposed method also retain most of the dynamical properties of the original systems, as demonstrated for instance by the preservation of the epidemic threshold in the multiplex susceptible-infected-susceptible model. These results suggest that information-theoretic approaches can be effectively employed for a more systematic analysis of static and time-varying multidimensional complex systems.Andrea SantoroVincenzo NicosiaAmerican Physical SocietyarticlePhysicsQC1-999ENPhysical Review X, Vol 10, Iss 2, p 021069 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999
spellingShingle	Physics QC1-999 Andrea Santoro Vincenzo Nicosia Algorithmic Complexity of Multiplex Networks
description	Multilayer networks preserve full information about the different interactions among the constituents of a complex system, and have recently proven quite useful in modeling transportation networks, social circles, and the human brain. A fundamental and still open problem is to assess if and when the multilayer representation of a system provides a qualitatively better model than the classical single-layer aggregated network. Here we tackle this problem from an algorithmic information theory perspective. We propose an intuitive way to encode a multilayer network into a bit string, and we define the complexity of a multilayer network as the ratio of the Kolmogorov complexity of the bit strings associated to the multilayer and to the corresponding aggregated graph. We find that there exists a maximum amount of additional information that a multilayer model can encode with respect to the equivalent single-layer graph. We show how our complexity measure can be used to obtain low-dimensional representations of multidimensional systems, to cluster multilayer networks into a small set of meaningful superfamilies, and to detect tipping points in the evolution of different time-varying multilayer graphs. Interestingly, the low-dimensional multiplex networks obtained with the proposed method also retain most of the dynamical properties of the original systems, as demonstrated for instance by the preservation of the epidemic threshold in the multiplex susceptible-infected-susceptible model. These results suggest that information-theoretic approaches can be effectively employed for a more systematic analysis of static and time-varying multidimensional complex systems.
format	article
author	Andrea Santoro Vincenzo Nicosia
author_facet	Andrea Santoro Vincenzo Nicosia
author_sort	Andrea Santoro
title	Algorithmic Complexity of Multiplex Networks
title_short	Algorithmic Complexity of Multiplex Networks
title_full	Algorithmic Complexity of Multiplex Networks
title_fullStr	Algorithmic Complexity of Multiplex Networks
title_full_unstemmed	Algorithmic Complexity of Multiplex Networks
title_sort	algorithmic complexity of multiplex networks
publisher	American Physical Society
publishDate	2020
url	https://doaj.org/article/4c65c4f23944489bb51018a5bfef0812
work_keys_str_mv	AT andreasantoro algorithmiccomplexityofmultiplexnetworks AT vincenzonicosia algorithmiccomplexityofmultiplexnetworks
_version_	1718395757356122112

Algorithmic Complexity of Multiplex Networks

Ejemplares similares