Эволюционные уравнения и случайные графы
https://doi.org/10.22405/2226-8383-2018-19-4-103-117
Аннотация
На примере эволюции случайного графа обсуждается подход к стохастической динамике сложных систем на основе эволюционных уравнений. Для случая графа эти уравнения описывают временные изменения в структуре графа, связанные с процессом случайного добавления в него новых связей. Такой процесс тесно связан с коалесценцией отдельных неприводимых компонент графа и ведет к появлению сингулярностей в спектрах и их моментах в течение конечных промежутков времени. Эти сингулярности возникают вследствие появления гигантской связной компоненты, порядок которой сравним с полным порядком всего графа. В работе демонстрируется метод анализа динамики процесса эволюции случайного графа, основанный на точном решении эволюционного уравнения, которое описывает зависимость от времени производящего функционала для вероятности застать в системе заданное распределение связных компонент графа. Дан вывод нелинейного интегрального уравнения для производящей функции распределения по числу связных компонент и обрисованы методы его анализа. В заключительной части обсуждены возможности применения изложенного подхода для решения ряда эволюционных проблем статистической геодинамики.
Об авторе
А. А. ЛушниковРоссия
Лушников Алексей Алексеевич — доктор физико-математических наук, главный научный сотрудник
Список литературы
1. Krapivsky, 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.82040
2. Lushnikov, A.A. Time evolution of a random graphs // J. Phys. A, 2005, vol. 38, pp L777.
3. Ben-Naim, E., & P. L. Krapivsky. Kinetic theory of random graphs: From paths to cycles // Physical Review, 2005, E 71.2 : 026129.
4. Ben–Naim E. & P.L. Krapivsky, Unicyclic components in random graphs // J. Phys., 2004, A 37, L189 (2004).
5. Lushnikov, A. A. Exactly solvable model of a coalescing random graph // Physical Review, 2015, vol. 91, p. 02211
6. Erd¨os, R & R´enyi, A., On the random graphs // A Magiar Tydomanyos Akatemia Matematikai Kutato Intezetenek Kцzlemenyei, 1960, 5, 17–61.
7. Bollobas, B., Random Graphs: (2nd ed.). 2001. Cambridge University Press. ISBN 0-521-797225.
8. Albert, R., & Barab´asi, A–L., Statistical mechanics of complex networks // Rev. Mod. Phys., 2002, 74, 47–97.
9. Newman, M. E. J., Networks: An Introduction. 2010, Oxford.
10. Cohen, R. & Havlin, S. Complex networks: structure, robustness and function. // Cambridge university press. 2010.
11. 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, 125
12. Stockmayer, W.H. Theory of molecular size distribution and gel formation in branched-chain polymers, //J. Chem. Phys. Vol. 11, p. 45.
13. Ziff, R. M. & Stell, G., Kinetics of polymer gelation // J. Chem. Phys., 1980, Vol. 73, 3492– 3499.
14. Marcus, A.H., Stochasic coalescence // Technometrics, 1968, 10, 133–143.
15. 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.
16. Leyvraz, F., Scaling theory and exactly solved models in the kinetics of irreversible aggregation // Phys. Rep., 2003, Vol. 383, 95–212.
17. Lushnikov A.A., Coagulation in finite systems, // J. Colloid Interface Sci., 1978, Vol. 65 276– 285.
18. Lushnikov A.A., From sol to gel exactly // Phys. Rev. Lett., 2004, Vol. 93, 198302.
19. Lushnikov A.A., Sol–gel transition in coagulating systems //Physica D, 2006, Vol. 222, 37.
20. Knuth, D.E., Linear probing and graphs // Algorithmica, 1998, Vol. 22 561–568.
21. Kreweras, G., Une famille de polynomes ayant pluseurs proprietes enumeratives // Period. Math.Hungar., 1980, Vol. 11 309–320.
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. 1953, Vol. 21 2056–2064.
Рецензия
Для цитирования:
Лушников А.А. Эволюционные уравнения и случайные графы. Чебышевский сборник. 2018;19(4):103-117. https://doi.org/10.22405/2226-8383-2018-19-4-103-117
For citation:
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