Percolation Properties of Complex Networks

Abstract

This dissertation is devoted to the study of connectivity transitions in complex networks via classical and new percolation models. Networks of high complexity appear across many domains; from commerce, telecommunication, infrastructure, and society, to gene regulation, and even evolution. In many cases these networks exhibit a sudden emergence (or breakdown) of long-range connectivity as a result of local microscopic events; this is of particular importance since their proper functioning often relies crucially on connectivity. One of the well-developed theories that deals with the formation of connected clusters as a result of random microscopic interactions, is percolation theory. This theory has been frequently applied to the study of epidemics and connectivity in complex networks; however details of most spreading phenomena are more involved, and the minimal assumptions of ordinary percolation are not adequate to describe many of their features. Hence it is necessary to design generalized models of percolation to accommodate more layers of complexity in the study of epidemics and connectivity. In this thesis we try to develop and explore new models of percolation by relaxing the main two assumptions of ordinary percolation, namely independence and locality of interactions. One of the new models we propose is agglomerative percolation, where we let clusters grow along all their boundary instead of a single site. This modification in most cases leads to a novel type of percolation that is in a different universality class than the ordinary type. We study agglomerative transitions on several graphs to extract their scaling properties and critical exponents. We show that agglomerative percolation maps onto random sequential renormalization, a method we developed to study the renormalization group flow of networks, and argue that contrary to previous claims, at least some of the scaling observed in previous renormalization schemes is due to agglomerative percolation rather than an underlying fractality in the structure of networks. In a new class of percolation models called explosive percolation, we show that the sharp transitions observed in numerical data is an artifact of the finite system sizes in computer simulations, and these transitions are actually continuous. We also contribute to the ongoing challenges in the study of percolation properties of interdependent networks by developing an analytical framework based on epidemic spreading. Finally, we develop cooperative percolation which can be applied to diverse settings, and show that adding cooperative effects to percolation models can change percolation properties dramatically; thus cooperativity --- which is in fact present in many social and physical phenomena --- needs to be considered in modeling these systems.