Authors А.А. Kochkarov, L.I. Sennikova, R.А. Kochkarov
Month, Year 01, 2015 @en
Index UDC 519.178
Abstract The concept of dynamic graph is introduced in the paper. Dynamic graph is defined as a sequence of "classic" (stationary) graphs, the transition between which are the complex and simple operations. The sequence of graphs forms a trajectory of the dynamic graph. Demonstrated that prefractal (fractal) graphs according to their definition are special case (sub-class) of dynamic graphs. Some properties of the dynamic graphs are reviewed. Dynamic graph is presented in this paper as a model of dynamic network, i.e. network that changes topology of relationships between its subscribers. Since one of the key metric characteristics of graphs is the diameter, strictly justified conditions for save diameter in the trajectory of the dynamic graph with the transit operation are presented also in the paper. As this operation, connection to graph a new vertex by one or more ribs is used. The interpretation of the hypothesis of "six handshakes" is shown from a position of dynamic theory of graphs. Justification of this hypothesis is suggested for "idealized" case. The question of inheritance in the trajectory of the dynamic graph is considered in context of preserving the metric characteristics. It is shown that diameter is able to maintain its value in a certain range with using proposed operations for transitions in the trajectory of dynamic graph, regardless of growth the number of the graph vertices. This important property has been applied widely to construct interaction algorithms of mobile agents when preservation of connectivity in network topology and preservation (not increase) the diameter of the network are required. The present work aims to demonstrate the potential of the emerging dynamic graph theory as a theoretical basis and for design algorithms for interaction of mobile agents, and to study complex networks of different physical and technical backgrounds.

Download PDF

Keywords Dynamic graphs; dynamic network; network systems; the diameter of the graph; hypothesis of "six handshakes"; network to the mobile users.
References 1. Westaby J.D. Dynamic Network Theory: How Social Networks Influence Goal. American Psychological Association, 2011, 279 p.
2. Gubanov D.A., Novikov D.A., Chkhartishvili A.G. Seti: modeli informatsionnogo vliyaniya, upravleniya i protivoborstva [Network: models of information influence, control and warfare]. Moscow: Fizmatlit, 2010, 228 p.
3. Kucheryavyy A.E., Prokop'ev A.V., Kucheryavyy E.A. Samoorganizuyushchiesya seti [Samoorganizuyuschejsya network]. St. Petersburg: Izd-vo «Lyubavich», 2011, 311 p.
4. Goldsmit A., Medar M., Effros M. Samoorganizuyushchiesya besprovodnye seti [Self-organizing wireless networks], V mire nauki [In the world of science], 2012, No. 6, pp. 76-81.
5. Sheresheva M.Yu. Formy setevogo vzaimodeystviya kompaniy. Kurs lektsiy [Forms of networking companies. A course of lectures]. Moscow: Izd. dom Gos. un-ta – Vysshey shkoly ekonomiki, 2010, 339 p.
6. Vizgunov A.N., Gol'dengorin B.I., Zamaraev V.A., Kalyagin V.A., Koldanov A.P., Koldanov P.A., Pardalos P.M. Primenenie rynochnykh grafov k analizu fondovogo rynka Rossii [The application of market-based graphs to the analysis of the Russian stock market], Zhurnal Novoy ekonomicheskoy
assotsiatsii [Journal of the New economic Association], 2012, No. 3 (15), pp. 66-81.
7. Georg C. The effect of the interbank network structure on contagion and common shocks, Journal of Banking & Finance, 2013.
8. Emelichev V.A., Mel'nikov O.I., Sarvanov V.I., Tyshkevich R.I. Lektsii po teorii grafov [Lectures on the theory of graphs]. Moscow: URSS, 2009, 392 p.
9. Kochkarov A.A. Strukturnaya dinamika: svoystva i kolichestvennye kharakteristiki predfraktal'nykh grafov [Structural dynamics: properties and quantitative characteristics of prefractal graphs]. Moscow: Vega-Info, 2012, 120 p.
10. Podlazov A.V., Shchetinina D.P. Model' rosta sotsial'noy seti [The growth model of the social network] Preprinty-IPM im. M.V. Keldysha [Preprinted them. M.V. Keldysh], 2013, No. 95,
16 p. Available at: preprint.asp?id=2013-95.
11. Uilson R. Vvedenie v teoriyu grafov [Introduction to graph theory]. Moscow: Mir, 1977, 208 p.
12. Krцn B. Growth of self-similar graphs, J. Graph Theory, 2004, No. 45 (3), pp. 224-239.
13. Rozenfeld H.D., Gallos L.K, Song Ch., Makse H.A. Fractal and Transfractal Scale-Free Networks. Mathematics of Complexity and Dynamical Systems. Edited by Robert A. Meyers. New York: Springer, 2012, 1858 p.
14. Milgram S. The small world problem, Psychology Today,1967, No. 2, pp. 60-67.
15. Akhromeeva T.S. [i dr.]. Sinergetika i setevaya real'nost' [Synergetics and network reality], Preprinty IPM im. M.V. Keldysha [Keldysh Institute preprints them. M.V. Keldysh], 2013,
No. 34, 32 p. Available at:
16. Mitin N.A., Podlazov A.V., Shchetinina D.P. Issledovanie setevykh svoystv Zhivogo zhurnala [The study of network properties LiveJournal], Preprinty IPM im. M.V. Keldysha [Keldysh Institute preprints them. M.V. Keldysh], 2012, No. 78, 16 p. Available at:
17. Kochkarov A.A. Modelirovanie strukturno-dinamicheskikh protsessov v setetsentricheskikh sistemakh monitoringa [Modeling structural-dynamic processes in network-centric systems monitoring], Antenny [Antenna], 2013, No. 1, pp. 164-168.

Comments are closed.