This dissertation consists of two parts, with the common theme "Exploration on and of Networks". In Part I we investigate the theme "exploration on networks" by studying random walks on dynamic... Show moreThis dissertation consists of two parts, with the common theme "Exploration on and of Networks". In Part I we investigate the theme "exploration on networks" by studying random walks on dynamic random graphs. Random walks can be seen as a model for exploration on networks. In particular, we study the "mixing times" of random walks which is a measure of how fast the random walk explores the graph. In Part II we investigate the theme "exploration of networks" by studying the problem of union-complexity of random disk regions. This problem is related to the frequency assignment on wireless networks. In particular, we study average-case behaviour of union-complexity of random disk regions, which can be seen as a measure of complexity of a 'typical' wireless network. Show less
In this thesis, we extend the concept of null models as canonical ensembles of multi-graphs with given constraints and present new metrics able to characterize real-world layered systems based on... Show moreIn this thesis, we extend the concept of null models as canonical ensembles of multi-graphs with given constraints and present new metrics able to characterize real-world layered systems based on their correlation patterns. We make extensive use of the maximum-entropy method in order to find the analytical expression of the expectation values of several topological quantities; furthermore, we employ the maximum-likelihood method to fit the models to real datasets. One of the main contributions of the present work is providing models and metrics that can be directly applied to real data. We introduce improved measures of overlap between layers of a multiplex and exploit such quantities to provide a new network reconstruction method applicable to multi-layer graphs. It turns out that this methodology, applicable to a specific class of multi-layer networks, can be successfully employed to reconstruct the World Trade Multiplex. Furthermore, we illustrate that the maximum-entropy models also allow us to find the so-called backbone of a real network, i.e. the information which is irreducible to the single-node properties and is therefore peculiar to the network itself. We conclude the thesis moving our attention to a different dataset, namely the scientific publication system. Show less
Complex systems, from financial markets to the brain, exhibit heterogeneous structures and non-stationary dynamics. These characteristics manifest themselves in the diversity of the elements in a... Show moreComplex systems, from financial markets to the brain, exhibit heterogeneous structures and non-stationary dynamics. These characteristics manifest themselves in the diversity of the elements in a system, and in the changing behaviour over time. Capturing and understanding this heterogeneity via appropriate models, can have important implications not only for science, but also for societal challenges like predicting the next financial crisis or developing advanced brain imaging techniques. In this thesis, we use the maximum-entropy approach to introduce a new class of statistical models, which captures part of the observed structural and/or temporal heterogeneity in the system. The models are applied to various real-world complex systems, and are used to address different problems. Show less