Dynamic Graphs and Some of Their Applications

The article considers modern approaches to modeling network systems and networks with a dynamic nature in general. The paper presents a modern class of dynamic graphs with a description of their practical implementation. Basic or simple operations, including deletion or addition of vertices and edges, are presented as a procedure for changing a dynamic graph. A special subclass of prefractal graphs with self-similarity properties is identified. For the class of dynamic graphs, the concept of a trajectory is defined, represented by a sequence of classical graphs changing from one to another in timeline. The toolkit of dynamic graphs can become the base for developing algorithms for command-information interaction of mobile subscribers in network systems, including network systems of continuous spatial monitoring. To describe optimization problems on multi-weighted graphs, a formal statement of a multi-criteria problem on a prefractal graph is proposed. Sets of feasible solutions, Pareto-optimal and complete solutions are described. Some lemmas of multicriterial optimization for individual problems that have the property of completeness are proposed, as well as restrictions on the linear convolution of criteria for finding Pareto-optimal solutions. The hereditary properties that manifest themselves in the trajectories of a dynamic graph are investigated, namely, the heredity of structural and functional characteristics and, as a result, the heredity of decisions during the transition from one graph to another in the trajectory of a dynamic graph. This work contributes to the development of network science and the theory of dynamic networks, offering both approaches and particular solutions on general and special classes of graphs.

1. Roberts F. S. Discrete Mathematical Models with Applications to Social, Biological, and Ecological Problems. Transl. from Eng. Moscow: Nauka; 1986. 494 p. (In Russ.).

2. Westaby J. D. Dynamic Network Theory: How Social Networks Influence Goal. American Psychological Association; 2011. 279 p.

3. Gubanov D.A., Novikov D.A., Chkhartishvili A. G. Social networks: Models of information influence, control and confrontation. Moscow: Fizmatlit; 2010. 228 p. (In Russ.).

4. Kucheryavy A. E., Prokopyev A. V., Kucheryavy E. A. Self-organizing networks. St. Petersburg: Lyubavich; 2011. 311 p. (In Russ.).

5. Goldsmith A., Medar M., Effros M. Self-organizing wireless networks. V mire nauki. 2012;(6):76–81. URL: https://www.elibrary.ru/ocsgzt (In Russ.).

6. Vizgunov A. N., Goldengorin B. I., Zamaraev V. A., et. al. Application of market graphs to the analysis of the Russian stock market. New Economic Journal. 2012;3(15):66–81. URL: https://www.elibrary.ru/pfiuxn (In Russ.).

7. Georg C. P. The Effect of Interbank Network Structure on Contagion and Common Shocks. Journal of Banking & Finance. 2013;37(7):2216–2228. DOI: 10.1016/j.jbankfin.2013.02.032

8. Krön B. Growth of self-similar graphs. J. Graph Theory. 2004;45(3):224–239. DOI: 10.1002/jgt.10157

9. Kochkarov A. A. Structural Dynamics: Properties and Quantitative Characteristics of Prefractal Graphs. Moscow: Vega-Info; 2012. 120 p. (In Russ.).

10. Kochkarov A. A., Malinetsky G. G., Kochkarov R. A. Some Aspects of Dynamic Graph Theory. Computational Mathematics and Mathematical Physics. 2015;55(9):1623–1629. (In Russ.). DOI: 10.7868/S0044466915090094

11. Rozenfeld H. D., Gallos L. K., Song Ch., Makse H. A. Fractal and Transfractal Scale-Free Networks. Mathematics of Complexity and Dynamical Systems. Robert A. Meyers, ed. New York: Springer; 2012. 1858 p. DOI: 10.1007/978-0-387-30440-3_231

12. Kochkarov A. M. Recognition of fractal graphs. Algorithmic approach. Nizhniy Arkhyz: RAS SAO; 1998. 170 p. (In Russ.).

13. Kazantsev A. M., Kochkarov R. A., Timoshenko A. V., Sychugov A. A. Some approaches to assessing the functioning of structural-dynamic monitoring systems under external influences. The scientific journal Modeling, Optimization and Information Technology. 2021;4(35):14. (In Russ.). DOI: 10.26102/2310-6018/2021.35.4.005

14. Kochkarov R. A. Multicriteria Optimization Problems on Multiweighted Prefractal Graphs. Moscow: AkademInnovatsiya; 2014. 189 p. URL: https://www.elibrary.ru/tyiygd (In Russ.).

15. Perepelitsa V. A. Multicriteria Models and Methods for Optimization Problems on Graphs. LAP Lambert Academic Publishing; 2013. 336 p. URL: https://n.eruditor.one/file/1399011/ (In Russ.).

16. Pavlov D. A. Multicriteria Problem of Covering a Prefractal Graph with Simple Chains. Diss. Cand. Sci. (Phys.-Math.) Taganrog: Taganrog State Radio Engineering University; 2004. 110 p. URL: https://newdisser.ru/_avtoreferats/01002738834.pdf (In Russ.).

17. Milgram S. The Small World Problem. Psychology Today. 1967;(2):60–67. DOI: 10.1007/978-3-658-21742-6_94

18. Podlazov A. V., Shchetinina DP Social network growth model. Preprinty IPM im. M. V. Keldysha RAN. 2013;(95):1–16. URL: https://keldysh.ru/papers/2013/prep2013_95.pdf (In Russ.).

19. Mitin N. A., Podlazov A.V., Shchetinina D. P. Study of network properties of LiveJournal. Preprinty IPM im. M.V. Keldysha RAN. 2012;(78):1–16. URL: https://keldysh.ru/papers/2012/prep2012_78.pdf (In Russ.).