Artificial Intelligence

Algorithmic Complexity of Multiplex Networks

Friday, November 06, 2020, 11:00am - 12:00pm PSTiCal
This event is open to the public.
AI Seminar
Vincenzo Nicosia, Queen Mary University of London


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, proposing an intuitive way to encode a multilayer network into a bit string, and defining 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 this 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.


Vincenzo (Enzo) Nicosia got his PhD from the University of Catania in 2008, and then worked as a PDRA at the same university (2008-2011), at the University of Cambridge (2011-2012), and at Queen Mary University of London (2013-2015), before taking his current role as a Lecturer in Networks and Data Analysis in the School of Mathematical Science at QMUL. His research spans several aspects of network theory and applications, and focuses on the relationships between the structural properties of complex networks and the characteristics of dynamical processes occurring on networks. He has been working on static and time-varying networks, unbiased, biased and interacting random walks on graphs, the duality between networks and time series, and models of network formation and growth. His most recent contributions are in the field of multi- ayer network growth, structural and dynamical reducibility of multiplex networks, and meta-network modelling real-world systems. His current research includes network based approaches to information filtering in large-scale multi-dimensional data sets, and the usage of random walks and diffusion to quantify heterogeneity in spatial systems.  He has co-authored a textbook on complex networks with Cambridge University Press in 2017, and currently sits in the editorial board of Journal of Complex Networks, Complexity, and PLoS One.

« Return to Events