Evolutionary equations and random graphs
https://doi.org/10.22405/2226-8383-2018-19-4-103-117
Abstract
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.
About the Author
A. A. Lushnikov
Geophysical Center RAS
Russian Federation
Russian Federation
Lushnikov Alexey Alekseevich — D.Sc., Principal research scientist
References
1. Krapivsky, P. L., Redner, S. & Ben-Naim, E. 2010. "A Kinetic View of Statistical Physics". Cambridge Univ. Press, Cambridge. Mathematical Reviews (MathSciNet): MR2757286 Zentralblatt MATH: 1235.82040
2. Lushnikov, A.A. 2005, "Time evolution of a random graphs"J. Phys. A vol. 38, pp L777.
3. Ben-Naim, E., & P. L. Krapivsky. 2005, "Kinetic theory of random graphs: From paths to cycles."Physical Review E 71.2 : 026129.
4. Ben–Naim E. & P.L. Krapivsky, 2004 "Unicyclic components in random graphs"J. Phys. A 37, L189 (2004).
5. Lushnikov, A. A. 2015. "Exactly solvable model of a coalescing random graph"Physical Review vol. 91, p. 02211
6. Erd¨os, R & R´enyi, A., 1960, "On the random graphs"A Magiar Tydomanyos Akatemia Matematikai Kutato Intezetenek Kцzlemenyei 5, 17–61.
7. Bollobas, B., 2001. "Random Graphs: (2nd ed.). Cambridge University Press. ISBN 0-52179722-5.
8. Albert, R., & Barab´asi, A–L., 2002 "Statistical mechanics of complex networksRev. Mod. Phys. 74, 47–97.
9. Newman, M. E. J., 2010, "Networks: An Introduction". Oxford.
10. Cohen, R. & Havlin, S. 2010, "Complex networks: structure, robustness and function". – Cambridge university press.
11. Flory, P.J., 1941 "Molecular Size Distribution in Three Dimensional Polymers I. Gelation". J. Am. Chem.. Soc., Vol. 30, 3083. Flory, P.J. (1941). J. Am. Chem. Soc. 63, 3083 Stockmayer, Walter H.(1944). "Theory of Molecular Size Distribution and Gel Formation in Branched Polymers II. General Cross Linking". Journal of Chemical Physics. 12,4, 125
12. Stockmayer, W.H. "Theory of molecular size distribution and gel formation in branched-chain polymersJ. Chem. Phys. Vol. 11, p. 45.
13. Ziff, R. M. & Stell, G., 1980, "Kinetics of polymer gelation J. Chem. Phys., Vol. 73, 3492–3499.
14. Marcus, A.H., 1968, "Stochasic coalescenceTechnometrics, 10, 133–143.
15. Aldous, D.J., 1999 "Deterministic and stochastic models for coalescence (aggregation, coagulation; review of the mean–field theory for probabilists"), Bernoulli Vol. 5 3–122.
16. Leyvraz, F., 2003, "Scaling theory and exactly solved models in the kinetics of irreversible aggregationPhys. Rep. Vol. 383, 95–212.
17. Lushnikov A.A., 1978, "Coagulation in finite systemsJ. Colloid Interface Sci., Vol. 65 276–285.
18. Lushnikov A.A., 2004, "From sol to gel exactly"Phys. Rev. Lett., Vol. 93, 198302.
19. Lushnikov A.A., 2006, "Sol–gel transition in coagulating systems"Physica D Vol. 222, 37.
20. Knuth, D.E., 1998, "Linear probing and graphstextit Algorithmica, Vol. 22 561–568.
21. Kreweras, G., 1980, "Une famille de polynomes ayant pluseurs proprietes enumerativesPeriod. Math.Hungar., Vol. 11 309–320.
22. Riddell R.J. & Ulenbeck G.E., 1953, On the Theory of the Virial Development of the Equation of State of Monoatomic Gases J. Chem. Phys. Vol. 21 2056–2064.
Review
For citations:
Lushnikov A.A. Evolutionary equations and random graphs. Chebyshevskii Sbornik. 2018;19(4):103-117. (In Russ.) https://doi.org/10.22405/2226-8383-2018-19-4-103-117
Views:
702
Email this article 