Algorithmic complexity of multiplex networks

Abstract

Multilayer networks preserve full information about the different interactions among the constituents of a complex system, and have recently proven quite useful in modelling 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 super-families, 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 SIS 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.

arXiv comment28 pages, 17 figures, 3 tables

References in corpus (34)

• Maps of random walks on complex networks reveal community structure
• Catastrophic cascade of failures in interdependent networks
• Epidemic processes in complex networks
• Synchronization in complex networks
• The structure and dynamics of multilayer networks
• Dynamical interplay between awareness and epidemic spreading in multiplex networks
• Diffusion dynamics on multiplex networks
• Mathematical Formulation of Multi-Layer Networks
• Structural measures for multiplex networks
• The physics of spreading processes in multilayer networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Emergence of network features from multiplexity
• The Statistical Physics of Real-World Networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Contact-based Social Contagion in Multiplex Networks
• Measuring and modelling correlations in multiplex networks
• The entropy of randomized network ensembles
• Community detection, link prediction, and layer interdependence in multilayer networks
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Multilayer motif analysis of brain networks
• Collective phenomena emerging from the interactions between dynamical processes in multiplex networks
• Mapping multiplex hubs in human functional brain network
• A framework for epidemic spreading in multiplex networks of metapopulations
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Irreducibility of multilayer network dynamics: the case of the voter model
• The effects of network structure, competition and memory time on social spreading phenomena
• Reconstructing networks with unknown and heterogeneous errors
• Efficient exploration of multiplex networks
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Accurate and scalable social recommendation using mixed-membership stochastic block models
• Layer Communities in Multiplex Networks
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Pareto optimality in multilayer network growth

Cited by in corpus (3)

• Optimal percolation in correlated multilayer networks with overlap
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Multiplex reconstruction with partial information