Phd in PHYSICS

Thesis title: Extended-range percolation and complex networks

This PhD thesis focuses on percolation in random graphs, extended-range percolation in simple and multiplex networks, an exactly solvable model for highly clustered random networks, and a problem of quantum networks optimization. In the first part of the thesis, a general introduction to percolation theory is provided, with an emphasis on percolation critical properties. The focus is quickly shifted to percolation in random graphs with arbitrary degree distributions and its critical behavior. Most of the results presented are known - apart from critical amplitude ratios, computed here for the first time - but they are rather scattered in the literature. Here a unified framework allows us to compute all percolation critical exponents in uncorrelated random graphs, and then check the validity of scaling relations among them. Large-scale numerical simulations reveal a nontrivial and unexpected finite-size scaling behavior for networks with a power-law degree distribution. In the second part of the thesis, we introduce and study the model of extended-range percolation. In this model, active nodes can directly communicate not only with active neighbors, but with all other active nodes at topological distance at most R from them. We first derive a heuristic solution of extended-range percolation in uncorrelated random graphs using the generating functions formalism, which allows us to study the critical behavior and to compute the critical exponents. This solution, however, is rather involved and not easily generalizable for high values of R. We then use a different approach to the problem, based on message-passing equations, which allows us to solve for arbitrary values of R. This solution allows us to solve the model on any given network and for any realization of the node activation process, and it is exact in the thermodynamic limit for locally tree-like networks. Using the message-passing formalism, we define extended-range percolation in multiplex networks, and we provide the exact solution for multiplex in which the layers are uncorrelated random graphs and there is a negligible link overlap. The competition between the increased fragility caused by interdependencies and the reinforcing effect of the extended-range mechanism reveals a nontrivial phase diagram and novel percolation behavior with a reentrant phase. In the third part, a simple model to generate random graphs with high clustering via triadic closure is presented. In this model we are able to compute all motifs densities exactly, revealing some interesting unexpected behaviors in networks with a power-law degree distribution. A comparison between the predictions of this model and the observation in real-world networks is also presented. Finally, a brief discussion of a parallel project on an optimization problem arising in quantum communication networks is presented, with a definition of the problem and an overview of the main findings.