Information-theoretic complexity of multiplex networks

The multiplex network paradigm has proven quite useful in the study of many real-world complex systems, by allowing to retain full information about the several kind of relationships among the elements of a system. However, to date there is not any established way of comparing the structural complexity of two multiplex networks. In this work, we use techniques inspired by algorithmic information theory to define a new metric for evaluating the information complexity of a multiplex network.
Using a simple encoding scheme based on prime numbers that transforms a multiplex network into a binary string, we define a measure to evaluate the information complexity of a multiplex network by means of the Kolmogorov complexity. We study the behaviour of the Kolmogorov complexity in an ensemble of synthetic multiplex networks, finding that there exists an optimal amount of additional information that a multiplex can encode with respect to the corresponding aggregate graph. We then compare and classify 22 real-world multiplex networks extracting lower-dimensional representations based on the proposed complexity and another structural descriptor.
Our results suggest that information-theoretic approaches and measures can be effectively employed in the study of multiplex networks, and pave the way for a more systematic analysis and comparison of multi-dimensional complex systems.