Percolation and reinforcement on complex networks

Abstract

Complex networks appear in almost every aspect of our daily life and are widely studied in the fields of physics, mathematics, finance, biology and computer science. This work utilizes percolation theory in statistical physics to explore the percolation properties of complex networks and develops a reinforcement scheme on improving network resilience. This dissertation covers two major parts of my Ph.D. research on complex networks: i) probe—in the context of both traditional percolation and k-core percolation—the resilience of complex networks with tunable degree distributions or directed dependency links under random, localized or targeted attacks; ii) develop and propose a reinforcement scheme to eradicate catastrophic collapses that occur very often in interdependent networks.

We first use generating function and probabilistic methods to obtain analytical solutions to percolation properties of interest, such as the giant component size and the critical occupation probability. We study uncorrelated random networks with Poisson, bi-Poisson, power-law, and Kronecker-delta degree distributions and construct those networks which are based on the configuration model. The computer simulation results show remarkable agreement with theoretical predictions.

We discover an increase of network robustness as the degree distribution broadens and a decrease of network robustness as directed dependency links come into play under random attacks. We also find that targeted attacks exert the biggest damage to the structure of both single and interdependent networks in k-core percolation. To strengthen the resilience of interdependent networks, we develop and propose a reinforcement strategy and obtain the critical amount of reinforced nodes analytically for interdependent Erdős-Rényi networks and numerically for scale-free and for random regular networks. Our mechanism leads to improvement of network stability of the West U.S. power grid.

This dissertation provides us with a deeper understanding of the effects of structural features on network stability and fresher insights into designing resilient interdependent infrastructure networks.