chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2018-19-4-103-117cheb-447Research ArticleСтатьиArticleЭволюционные уравнения и случайные графыEvolutionary equations and random graphsЛушниковА. А.LushnikovA. A.

Лушников Алексей Алексеевич — доктор физико-математических наук, главный научный сотрудник

Lushnikov Alexey Alekseevich — D.Sc., Principal research scientist

alex.lushnikov@mail.ruГеофизический центр РАНРоссияGeophysical Center RASRussian Federation201804112018194103117Copyright © Лушников А.А., 20192019Лушников А.А.Lushnikov A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/447

На примере эволюции случайного графа обсуждается подход к стохастической динамике сложных систем на основе эволюционных уравнений. Для случая графа эти уравнения описывают временные изменения в структуре графа, связанные с процессом случайного добавления в него новых связей. Такой процесс тесно связан с коалесценцией отдельных неприводимых компонент графа и ведет к появлению сингулярностей в спектрах и их моментах в течение конечных промежутков времени. Эти сингулярности возникают вследствие появления гигантской связной компоненты, порядок которой сравним с полным порядком всего графа. В работе демонстрируется метод анализа динамики процесса эволюции случайного графа, основанный на точном решении эволюционного уравнения, которое описывает зависимость от времени производящего функционала для вероятности застать в системе заданное распределение связных компонент графа. Дан вывод нелинейного интегрального уравнения для производящей функции распределения по числу связных компонент и обрисованы методы его анализа. В заключительной части обсуждены возможности применения изложенного подхода для решения ряда эволюционных проблем статистической геодинамики.

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.

эволюционные уравненияконечные случайные графыциклыevolutionary equationsfinite random graphscyclesГосударственное задание ГЦ РАНReferencesKrapivsky, P. L., Redner, S. & Ben-Naim, E. A Kinetic View of Statistical Physics // Cambridge Univ. Press, Cambridge. 2010. Mathematical Reviews (MathSciNet): MR2757286 Zentralblatt MATH: 1235.82040Krapivsky, 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.82040Lushnikov, A.A. Time evolution of a random graphs // J. Phys. A, 2005, vol. 38, pp L777.Lushnikov, A.A. 2005, "Time evolution of a random graphs"J. Phys. A vol. 38, pp L777.Ben-Naim, E., & P. L. Krapivsky. Kinetic theory of random graphs: From paths to cycles // Physical Review, 2005, E 71.2 : 026129.Ben-Naim, E., & P. L. Krapivsky. 2005, "Kinetic theory of random graphs: From paths to cycles."Physical Review E 71.2 : 026129.Ben–Naim E. & P.L. Krapivsky, Unicyclic components in random graphs // J. Phys., 2004, A 37, L189 (2004).Ben–Naim E. & P.L. Krapivsky, 2004 "Unicyclic components in random graphs"J. Phys. A 37, L189 (2004).Lushnikov, A. A. Exactly solvable model of a coalescing random graph // Physical Review, 2015, vol. 91, p. 02211Lushnikov, A. A. 2015. "Exactly solvable model of a coalescing random graph"Physical Review vol. 91, p. 02211Erd¨os, R & R´enyi, A., On the random graphs // A Magiar Tydomanyos Akatemia Matematikai Kutato Intezetenek Kцzlemenyei, 1960, 5, 17–61.Erd¨os, R & R´enyi, A., 1960, "On the random graphs"A Magiar Tydomanyos Akatemia Matematikai Kutato Intezetenek Kцzlemenyei 5, 17–61.Bollobas, B., Random Graphs: (2nd ed.). 2001. Cambridge University Press. ISBN 0-521-797225.Bollobas, B., 2001. "Random Graphs: (2nd ed.). Cambridge University Press. ISBN 0-52179722-5.Albert, R., & Barab´asi, A–L., Statistical mechanics of complex networks // Rev. Mod. Phys., 2002, 74, 47–97.Albert, R., & Barab´asi, A–L., 2002 "Statistical mechanics of complex networksRev. Mod. Phys. 74, 47–97.Newman, M. E. J., Networks: An Introduction. 2010, Oxford.Newman, M. E. J., 2010, "Networks: An Introduction". Oxford.Cohen, R. & Havlin, S. Complex networks: structure, robustness and function. // Cambridge university press. 2010.Cohen, R. & Havlin, S. 2010, "Complex networks: structure, robustness and function". – Cambridge university press.Flory, P.J., 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, 125Flory, 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, 125Stockmayer, W.H. Theory of molecular size distribution and gel formation in branched-chain polymers, //J. Chem. Phys. Vol. 11, p. 45.Stockmayer, W.H. "Theory of molecular size distribution and gel formation in branched-chain polymersJ. Chem. Phys. Vol. 11, p. 45.Ziff, R. M. & Stell, G., Kinetics of polymer gelation // J. Chem. Phys., 1980, Vol. 73, 3492– 3499.Ziff, R. M. & Stell, G., 1980, "Kinetics of polymer gelation J. Chem. Phys., Vol. 73, 3492–3499.Marcus, A.H., Stochasic coalescence // Technometrics, 1968, 10, 133–143.Marcus, A.H., 1968, "Stochasic coalescenceTechnometrics, 10, 133–143.Aldous, D.J., Deterministic and stochastic models for coalescence (aggregation, coagulation; review of the mean–field theory for probabilists) // Bernoulli, 1999, Vol. 5 3–122.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.Leyvraz, F., Scaling theory and exactly solved models in the kinetics of irreversible aggregation // Phys. Rep., 2003, Vol. 383, 95–212.Leyvraz, F., 2003, "Scaling theory and exactly solved models in the kinetics of irreversible aggregationPhys. Rep. Vol. 383, 95–212.Lushnikov A.A., Coagulation in finite systems, // J. Colloid Interface Sci., 1978, Vol. 65 276– 285.Lushnikov A.A., 1978, "Coagulation in finite systemsJ. Colloid Interface Sci., Vol. 65 276–285.Lushnikov A.A., From sol to gel exactly // Phys. Rev. Lett., 2004, Vol. 93, 198302.Lushnikov A.A., 2004, "From sol to gel exactly"Phys. Rev. Lett., Vol. 93, 198302.Lushnikov A.A., Sol–gel transition in coagulating systems //Physica D, 2006, Vol. 222, 37.Lushnikov A.A., 2006, "Sol–gel transition in coagulating systems"Physica D Vol. 222, 37.Knuth, D.E., Linear probing and graphs // Algorithmica, 1998, Vol. 22 561–568.Knuth, D.E., 1998, "Linear probing and graphstextit Algorithmica, Vol. 22 561–568.Kreweras, G., Une famille de polynomes ayant pluseurs proprietes enumeratives // Period. Math.Hungar., 1980, Vol. 11 309–320.Kreweras, G., 1980, "Une famille de polynomes ayant pluseurs proprietes enumerativesPeriod. Math.Hungar., Vol. 11 309–320.Riddell R.J. & Ulenbeck G.E., On the Theory of the Virial Development of the Equation of State of Monoatomic Gases // J. Chem. Phys. 1953, Vol. 21 2056–2064.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.

The authors declare that there are no conflicts of interest present.