Cyclization in bipartite random graphs

In this paper the time evolution of a finite bipartite graph initially comprising two sorts of isolated vertices is considered. The graph is assumed to evolve by adding edges, one at a time. Each new edge connects either two linked components and forms a new component of a larger order (coalescence of graphs) or increases (by one) the number of edges in a given linked component (cycling). Any state of the graph is thus characterized by the set of occupation numbers (the numbers of linked components comprising a given numbers of vertexes of the both sorts and a given number of edges. Once the rate of appearance of an extra edge in the graph being known, the master equation governing the time evolution of the probability to find the random graph in a given state is reformulated in terms of the functional generating the probability to find the evolving graph in a given state. The exact solution of the evolution equation for the generating functional applies for analyzing the average population numbers of linked components. In the limit of large order of the graph the distribution factorizes into two multipliers, one of which is just the spectrum of linked components in the infinite bipartite graph, The second multiplier includes the dependence on the total size of the graph. Both these multipliers contain information on the emergence of the giant component that forms at a critical time.

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 γ distributed over g with the algebraic prefactor g-5/2. The coalescence process is shown to terminate by the formation of the steady-state γ spectrum with the same algebraic prefactor.

Exactly solvable model of a coalescing random graph

An initially empty (no edges) graph of order M evolves by randomly adding one edge at a time. This edge connects either two linked components and forms a new component of larger order (coalescence of graphs) or increases (by one) the number of edges in a given linked component (cycling). Assuming that the vertices of the graph 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 by applying the generating function method. 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 kinetics of growth of this component is studied for arbitrary initial conditions. Found are the time dependences of the average order and the valence of the giant component. The distribution over orders and valences of the linked components of the graph is derived for an initially empty graph comprising M bare polyvalent vertices.