Dynamic Graphs and Some of Their Applications

Abstract

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.

Affiliated Institutions

• Russian Academy of Sciences RU
• Financial University RU

Related Publications