Evolutionary equations and random graphs

A. A. Lushnikov

Čebyševskij sbornik, Tome 19 (2018) no. 4, pp. 103-117.

Résumé

An example of the evolution of a random graph is used to discuss the approach to stochastic dynamics of complex systems based on evolutionary equations. For the case of a graph, these equations describe temporal changes in the structure of the graph associated with the process of randomly adding new bonds to it. Such a process is closely related to the coalescence of individual irreducible components of the graph and leads to the appearance of singularities in the spectra and their moments during finite time intervals. These singularities arise due to the appearance of a giant connected component whose order is comparable with the total order of the entire graph. The paper demonstrates a method for analyzing the dynamics of the process of evolution of a random graph based on the exact solution of an evolutionary equation that describes the time dependence of the generating functional for the probability of finding in the system a given distribution of connected components of the graph. A derivation of the nonlinear integral equation for the generating function distribution on the number of connected components is given and outlined the methods of its analysis. In the concluding part, the possibilities of applying this approach to solving a number of evolutionary problems of statistical geodynamics are discussed.

Détail

Keywords: evolutionary equations, finite random graphs, cycles.

Bibliographie

[1] Krapivsky P. L., Redner S., Ben-Naim E., A Kinetic View of Statistical Physics, Cambridge Univ. Press, Cambridge, 2010 | MR | Zbl

[2] Lushnikov A. A., “Time evolution of a random graphs”, J. Phys. A, 38 (2005), L777 | MR | Zbl

[3] Ben-Naim E., Krapivsky P. L., “Kinetic theory of random graphs: From paths to cycles”, Physical Review E, 71:2 (2005), 026129 | MR

[4] Ben-Naim E., Krapivsky P. L., “Unicyclic components in random graphs”, J. Phys., A 37 (2004), L189 | MR | Zbl

[5] Lushnikov A. A., “Exactly solvable model of a coalescing random graph”, Physical Review, 91 (2015), 02211 | MR

[6] Erdös R., Rényi A., “On the random graphs”, A Magiar Tydomanyos Akatemia Matematikai Kutato Intezetenek Kzlemenyei, 5 (1960), 17–61 | MR | Zbl

[7] Bollobas B., Random Graphs, 2nd ed., Cambridge University Press, 2001 | MR | Zbl

[8] Albert R., Barabási A.-L., “Statistical mechanics of complex networks”, Rev. Mod. Phys., 74 (2002), 47–97 | MR | Zbl

[9] Newman M. E. J., Networks: An Introduction, Oxford, 2010 | MR | Zbl

[10] Cohen R., Havlin S., Complex networks: structure, robustness and function, Cambridge university press, 2010 | Zbl

[11] Flory P. J., “Molecular Size Distribution in Three Dimensional Polymers I. Gelation”, J. Am. Chem.. Soc., 30, 3083; Stockmayer W. H., “Theory of Molecular Size Distribution and Gel Formation in Branched Polymers II. General Cross Linking”, Journal of Chemical Physics, 12:4 (1944), 125

[12] Stockmayer W. H., “Theory of molecular size distribution and gel formation in branched-chain polymers”, J. Chem. Phys., 11, 45 | MR

[13] Ziff R. M., Stell G., “Kinetics of polymer gelation”, J. Chem. Phys., 73 (1980), 3492–3499 | MR

[14] Marcus A. H., “Stochasic coalescence”, Technometrics, 10 (1968), 133–143 | MR

[15] Aldous D. J., “Deterministic and stochastic models for coalescence (aggregation, coagulation; review of the mean–field theory for probabilists)”, Bernoulli, 5 (1999), 3–122 | MR

[16] Leyvraz F., “Scaling theory and exactly solved models in the kinetics of irreversible aggregation”, Phys. Rep., 383 (2003), 95–212

[17] Lushnikov A. A., “Coagulation in finite systems”, Colloid Interface Sci., 65 (1978), 276–285

[18] Lushnikov A. A., “From sol to gel exactly”, Phys. Rev. Lett., 93 (2004), 198302

[19] Lushnikov A. A., “Sol-gel transition in coagulating systems”, Physica D, 222 (2006), 37 | MR | Zbl

[20] Knuth D. E., “Linear probing and graphs”, Algorithmica, 22 (1998), 561–568 | MR | Zbl

[21] Kreweras G., “Une famille de polynomes ayant pluseurs proprietes enumeratives”, Period. Math. Hungar., 11 (1980), 309–320 | MR | Zbl

[22] Riddell R. J., Ulenbeck G. E., “On the Theory of the Virial Development of the Equation of State of Monoatomic Gases”, J. Chem. Phys., 21 (1953), 2056–2064 | MR