Goal of research
Significant progress in the analysis of network structures on the basis of new effective algorithms and technologies developed on the basis of modern and internationally recognized approaches. The main directions of the research were:
Study of robustness of network analysis algorithms in random variable networks.
Study of algorithmic complexity of optimization problems on networks (graphs)
Development and implementation of effective algorithms for solving optimization problems of high computational complexity.
Development of models and algorithms for data mining.
Tthe theoretical basis of the study is the work of the leading scientist P. M. Pardalos. The research methodology is based on the fundamental properties of large weighted graphs (networks) and optimization problems defined on them. Construction of heuristics for solving applied problems of transport and warehouse logistics is based on modern models and algorithms for solving problems of high computational complexity. The most modern methods of development of effective algorithms are used for the analysis of these problems. Modern methods of machine learning were used to analyze audio, photo and video information processing.
Empirical base of research
The empirical base of research on stock market networks were data on stock markets in different countries from the database yahoo finance. The empirical base of research on effective optimization algorithms was the generally accepted sets of benchmarks to test the effectiveness of algorithms (open access). The empirical base of research on models and algorithms of data mining were sets of experimental data obtained from scientific literature or independently with the help of conducted experiments.
Results of research
As the result of the research significant advances and new results were obtained in all scientific directions mentioned above.
Research in the first direction was focused on the study of the robustness (stability) of algorithms for identifying network structures in random variable networks. Using previously developed theory of random variable networks, an important problem of developing robust algorithms for identifying network structures has been solved. An approach to estimating the uncertainty of network structure identification based on the study of random variable networks is significantly developed. Confidence sets for the edges of a graph representing an important network structure for applications (threshold graph) are introduced and investigated. Stability of procedures for constructing confidence sets is investigated. A methodology for analyzing the stability of clustering algorithms in random variable networks is developed.
In the second direction, the research was related to the analysis of optimization problems on tree graphs and optimization problems under uncertainty. One of the tasks of the project was to describe graphs with the maximum (minimum) number of independent subsets in the graph. Significant progress has been made in this task. Tree graphs of diameter 6 and 7 with a minimum number of independent subsets, with a sufficiently large number of vertices, are fully described. It is shown that for all fixed values of the number of vertices and the diameter of the tree graph, the extremal tree is unique up to isomorphism.
For the shortest path problem under uncertainty, a new approach is developed and an original model for accounting for probabilistic uncertainty is constructed. The key feature of the proposed model is that instead of moment-based uncertainty sets that explicitly account for first-and second-order moments, standardized uncertainty sets are used. This allows to construct uncertainty sets from partially observed and unreliable data. It is shown that probabilistic constraints can be strengthened with the help of new available information and, therefore, can be adapted to a dynamic decision-making process. The presented theoretical and numerical results demonstrate the advantages of the proposed approach in comparison with standard robust and robust-stochastic optimization methods. It is shown that the quality of robust stochastic solutions depends on both the quality of the collected information and the structure of probability constraints. In particular, with the appropriate choice of parameters, robust stochastic solutions can provide a reasonable approximation of the optimal solution under full information conditions.
In the third area of research, the vehicles routing problem with split delivery, a heterogeneous fleet, and site dependence constraints was considered. Two new approaches have been developed for solving problems with hard constraints. The first approach uses the idea of "clustering first, vehicle routing next". The second approach is to determine the feasibility of each vehicle assignment when constructing a solution in constructive heuristic and exact algorithms. An original efficient algorithm for solving problems is proposed. In this algorithm, we assume that all customers are sorted by their classes (types) so that first customers belong to the class with the smallest set of vehicles, then customers with a wider set of vehicles, and so on. Clients of the same class can be sorted in descending order of their requirements. Similarly, vehicles are sorted starting from the smallest set of vehicles, and within each set, vehicles are sorted in ascending order of their value. It is shown that the proposed algorithm guarantees high-quality solutions to the most complex vehicle routing problems from the considered class that arise in real applications for which traditional approaches cannot find even feasible solutions.
In the fourth area of research, the methods and approaches developed in the project were applied to the analysis of stock market data. Network models of stock markets in different countries for different periods were considered and the robustness (stability) of algorithms for identifying the main characteristics of the networks was studied. Two models of the market network were considered. The first model is based on the classical Pearson correlation as a measure of the similarity between stock returns. The second model is based on the similarity of the signs of stock returns. The stability of identification procedures is investigated for the following characteristics of the market network: the distribution of edge weights, the distribution of vertex degrees in the market graph, clicks and independent sets of the market graph, and the distribution of vertex degrees of the maximum spanning tree. It is shown that statistical identification procedures based on the similarity of signs have the property of stability, in contrast to the procedures based on the classical Pearson correlation.
Level of implementation, recommendations on implementation or outcomes of the implementation of the results
The results obtained can be used in stock market analysis (methods of network market analysis), in bioinformatics (analysis of gene expression networks), in the theory and practice of decision-making (optimization under uncertainty), in practical problems of transport logistics (the problem of transport distribution).