Emergence of the giant weak component in directed random graphs with arbitrary degree distributions

The weak component generalizes the idea of connected components to directed graphs. In this paper, an exact criterion for the existence of the giant weak component is derived for directed graphs with arbitrary bivariate degree distributions. In addition, we consider a random process for evolving directed graphs with bounded degrees. The bounds are not the same for different vertices but satisfy a predefined distribution. The analytic expression obtained for the evolving degree distribution is then combined with the weak-component criterion to obtain the exact time of the phase transition. The phase-transition time is obtained as a function of the distribution that bounds the degrees. Remarkably, when viewed from the step-polymerization formalism, the new results yield Flory-Stockmayer gelation theory and generalize it to a broader scope.

Figure 1

An example illustrating how topologies of a directed graph and the undirected one satisfying an induced degree distribution may be drastically different. The directed graph on the left consists of vertices that have either one out-edge or two in-edges. The corresponding undirected graph on the right consists of vertices that have either one edge or two.

Figure 2

Construction of the implicit equation for $w\left(n\right),$ the function generating weak-component sizes.

Figure 3

Each vertex of the evolving directed graph is viewed as carrying two types of edges (in/out) and two types of vacant spots (also in/out). The initial number of vacant spots sets up a limit on the maximum number of incident edges for each vertex. The random process converts a pair of an in-spot and an out-spot belonging to different vertices into a directed edge.

Figure 4

Evolution of the bivariate degree distribution $u(n,k,t)$ for the random-graph model with bounded degrees. In this example, the initial distribution of bounds $P(n_{\text{max}},k_{\text{max}})$ vanishes everywhere except for the points $P(10,10)=\frac{1}{3},P(5,10)=\frac{1}{3},P(10,4)=\frac{1}{3}.$ Since the total number of in-spots exceeds the total number of out-spots, only $k$-marginal of the distribution approaches a linear combination of $\delta$ functions in the time limit, $t\to \infty .$ The time snapshots are obtained for the following values of time: (a) $t=0.01$, (b) $t=0.1$, (c) $t=1$, and (d) $t\to \infty .$

Figure 5

Barycentric plots for the weak-component phase-transition time in terms of $c_n,$ as obtained for the random-graph model with bounded degrees. Panels (a)–(i) present various initial distributions that are nonzero at three points, $n_{\text{max},i},k_{\text{max},i},i=1,2,3$. Cases (a) and (b) are covered by Flory-Stockmayer theory. The black area contains configurations that do not admit phase transition, the color (shaded) area contains configurations with finite phase transition, and the red dashed line contains configurations that admit the phase transition asymptotically at infinite time.