Percolation in random directed graphs with an arbitrary degree distribution

Abstract

Random graphs are probability spaces having graphs obeying predefined constraints as events. Sampling from such a space can be a challenge because of non-trivial dependencies that graph constraints may impose. An exotic observation that has been made in various random graphs is that small changes in the constraints may impose dramatic changes in the graph structure -- the phenomenon that is referred to as the phase transition. One example of such a small change is gradual removal of the edges (or vertices), also known as percolation. This work brings the notion of directionality to random graphs with a given degree sequence, by studying two aspects: 1) algorithmic construction of such random graphs and 2) percolation processes on vertices and edges.

For undirected graphs, the percolation threshold for existence of the giant component (a component whose size scales linearly in the total number of vertices) is derived by Jason (2009) and Fountoulakis (2007) who both built upon earlier results of Molloy and Reed (1995) about the existence of a giant component. We derive the percolation threshold for the existence of a giant strongly connected component for edge and vertex percolation by extending the results of Fountoulakis for undirected graphs and combining them with the Cooper and Frieze's (2004) existence criteria. By building on the results of Bayati, Kim and Saberi (2010), we then develop an algorithm that generates directed random graphs almost uniformly with runtime close to linear in the number of edges. Finally, we illustrate the theoretical results with numerical simulations.