Source-enhanced coalescence of trees in a random forest

The time evolution of a random graph with varying number of edges and vertices is considered. The edges and vertices are assumed to be added at random by one at a time with different rates. A fresh edge connects either two linked components and forms a new component of larger order $g$ (coalescence of graphs) or increases (by one) the number of edges in a given linked component (cycling). Assuming the vertices to have a finite valence (the number of edges connected with a given vertex is limited) the kinetic equation for the distribution of linked components of the graph over their orders and valences is formulated and solved exactly by applying the generating function method for the case of coalescence of trees. The evolution process is shown to reveal a phase transition: the emergence of a giant linked component whose order is comparable to the total order of the graph. The time dependencies of the moments of the distribution of linked components over their orders and valences are found explicitly for the pregelation period and the critical behavior of the spectrum is analyzed. It is found that the linked components are $\gamma$ distributed over $g$ with the algebraic prefactor $g^{-5/2}$. The coalescence process is shown to terminate by the formation of the steady-state $\gamma$ spectrum with the same algebraic prefactor.

Figure 1

The phase transition. Shown is the dependence of the order parameter $W\left(\tau \right)$, on the reduced time $\tau =(t-t_c)/t_c$, for different values of the vertex valence $s$. Solid, dash, and dash-dot curves correspond to $s=3, s=5$, and $s=7$, respectively.

Figure 2

Average forest valence $\tilde{S}\left(t\right)$ (solid curve), average forest order $\tilde{M}\left(t\right)$ (dash curve), and the average number of trees $\tilde{N}\left(t\right)$ (dash-dot curve) are shown as the functions of time. First two moments $\tilde{S}\left(t\right)$ and $\tilde{M}\left(t\right)$ have clearly expressed cusps at $t=t_c$, whereas $\tilde{N}\left(t\right)$ does not display any singularity at the critical time. The explanation of this fact is given in the text.

Figure 3

Time dependence of the average valence $\tilde{S}\left(t\right)$ of the forest at different values of the vertex valence $s$.

Figure 4

Shown are the moments $\tilde{S}\left(\infty \right)$ and $\tilde{M}\left(\infty \right)$ of the residual forest vs. $s$.