• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)SearchMenu

Research of robustness of network analysis algorithms

2020
Head: Kalyagin, Valery A., Pardalos, Panos M.

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:

  1. Study of robustness of network analysis algorithms in random variable networks.

  2. Study of algorithmic complexity of optimization problems on networks (graphs)

  3. Development and implementation of effective algorithms for solving optimization problems of high computational complexity.

  4. Development of models and algorithms for data mining.

Methodology

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).

Publications:


Kalyagin V. A., Slashchinin S. Uncertainty of Efficient Frontier in Portfolio Optimization, in: Lecture Notes in Computer Science, Learning and Intelligent Optimization, 14th International Conference on Learning and Intelligent Optimization (LION 2020). Switzerland : Springer, 2020. С. 371-376. 
Miasnikof P., Shestopaloff A. Y., Bonner A. J., Lawryshyn Y., Pardalos P. M. A density-based statistical analysis of graph clustering algorithm performance // Journal of Complex Networks. 2020. Vol. 8. No. 3. P. 1-33. doi
Mikhail V. B., Ekaterina K. B., Ilya S. B. NP-completeness of cell formation problem with grouping efficacy objective // International Journal of Production Research. 2020. Vol. 58. No. 20. P. 6159-6169. doi
Veselov S., Gribanov D., Zolotykh N., Chirkov A. A polynomial algorithm for minimizing discrete convic functions in fixed dimension // Discrete Applied Mathematics. 2020. Vol. 283. P. 11-19. doi
Gribanov D., Malyshev D. Minimization of even conic functions on the two-dimensional integral lattice // Journal of Applied and Industrial Mathematics. 2020. Vol. 14. No. 1. P. 56-72. doi
Manipur I., Granata I., Maddalena L., Guarracino M. R. Clustering analysis of tumor metabolic networks // BMC Bioinformatics. 2020. Vol. 21. No. 10. P. 349-. doi
Gokulnath P., de C. T., Manipur I., Di P. A. A., Guarracino M. R., Zannini M. Long Non-Coding RNA HAND2-AS1 Acts as a Tumor Suppressor in High-Grade Serous Ovarian Carcinoma // International Journal of Molecular Sciences. 2020. Vol. 21. No. 11. P. 1-17. doi
Savchenko V. V., Savchenko A. A Method for the Real-Time Updating of Voice Samples in the Unified Biometric System // Измерительная техника. 2020. Vol. 63. No. 5. P. 391-400. doi
Savchenko A. Probabilistic Neural Network With Complex Exponential Activation Functions in Image Recognition // IEEE Transactions on Neural Networks and Learning Systems. 2020. Vol. 31. No. 2. P. 651-660. doi
Savchenko A., Miasnikov E. V. Event Recognition Based on Classification of Generated Image Captions, in: Advances in Intelligent Data Analysis XVIII (IDA 2020). Cham : Springer, 2020. С. 418-430. 
Savchenko A. Event Recognition with Automatic Album Detection based on Sequential Grouping of Confidence Scores and Neural Attention, in: Proceedings of International Joint Conference on Neural Networks 2020 (IJCNN 2020). Piscataway : IEEE, 2020. С. 1-8. 
Savchenko A., Savchenko L., Savchenko V. Optimization of Gain in Symmetrized Itakura-Saito Discrimination for Pronunciation Learning, in: Mathematical Optimization Theory and Operations Research, 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, (Т. 12095). Cham : Springer, 2020. С. 440-454. 
Savchenko A. Sequential Analysis with Specified Confidence Level and Adaptive Convolutional Neural Networks in Image Recognition, in: Proceedings of International Joint Conference on Neural Networks 2020 (IJCNN 2020). Piscataway : IEEE, 2020. С. 1-8. 
Irina U., Olga B., Mikhail V. B. Fast Heuristic for Vehicle Routing Problem on Trees, in: Mathematical Optimization Theory and Operations Research. 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, Revised Selected Papers.: Springer, 2020. С. 379-386. 
Zhang Q., Guan X., Pardalos P. M. Maximum shortest path interdiction problem by upgrading edges on trees under weighted l1 norm // Journal of Global Optimization. 2021. Vol. 79. P. 959-987. doi
Taletskii D. Trees of Diameter 6 and 7 with Minimum Number of Independent Sets // Математические заметки. 2021. Vol. 109. P. 280-291. doi
Semenov D., Koldanov A. P., Koldanov P., Pardalos P. M. A robustness comparison of two market network models // IMA Journal Management Mathematics. 2022. Vol. 33. No. 1. P. 123-137. doi