• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Исследование устойчивости алгоритмов анализа сетевых структур

2020
Руководитель: Калягин Валерий Александрович, Пардалос Панагиотис Ор Панайоте

Цель работы

Cущественное продвижение в анализе сетевых структур на основе новых эффективных алгоритмов и технологий, разработанных на базе современных и признанных на мировом уровне подходов. Задачи работы были сгруппированы в техническом задании по четырем научным направлениям:

  1. Исследование устойчивости алгоритмов анализа сетевых структур в сетях случайных величин.

  2. Исследование алгоритмической сложности задач оптимизации на сетях (графах).

  3. Разработка и реализация эффективных алгоритмов решения задач оптимизации высокой вычислительной сложности.

  4. Разработка моделей и алгоритмов интеллектуального анализа данных.

Используемые методы

Теоретическую основу проведённого исследования составляют работы ведущего ученого П.М. Пардалоса. Методология исследований основана на фундаментальных свойствах больших взвешенных графов (сетей) и определенных на них задачах оптимизации. Построение эвристик для решения прикладных задач транспортной и складской логистики основано на современных моделях и алгоритмах решения задач высокой вычислительной сложности.  Для анализа поставленных задач используются самые современные методы разработки эффективных алгоритмов. Для анализа аудио, фото и видео информации использовались современные методы машинного обучения.

Эмпирическая база исследования

Эмпирической базой исследований сетей фондовых рынков были данные по фондовым рынкам различных стран из базы yahoo finance.  Эмпирической базой исследований по эффективным алгоритмам оптимизации были общепринятые наборы тестовых примеров (benchmarks) проверки эффективности алгоритмов (открытый доступ). Эмпирической базой исследований по моделям и алгоритмам интеллектуального анализа данных были наборы экспериментальных данных полученных из научной литературы или самостоятельно с помощью проведенных экспериментов. 

Результаты работы

В ходе выполнения технического задания были получены существенные продвижения и новые результаты по всем  научным направлениям. 

Исследования по первому направлению были сконцентрированы на исследовании устойчивости алгоритмов идентификации сетевых структур в сетях случайных величин. В области анализа сетей случайных величин решена важная проблема разработки устойчивых алгоритмов идентификации сетевых структур. Существенно развит подход к оценке неопределенности идентификации графовых моделей на основе  исследования сетей случайных величин. Введены и исследованы доверительные множества для ребер графа представляющего важную для приложений сетевую структуру (отсеченный граф). Исследована устойчивость процедур построения доверительных множеств. Разработана методология анализа устойчивости алгоритмов кластеризации в сетях случайных величин.

По второму направлению исследования были связаны с анализом задач оптимизации на графах деревьях и задач оптимизации в условиях неопределенности. Одной из задач проекта была  задача описания графов с максимальным (минимальным) числом независимых подмножеств в графе. Получено существенное продвижение по этой задаче. Полностью описаны графы-деревья диаметра 6 и 7 с минимальным числом независимых подмножеств, при достаточно большом числе вершин. Показано, что при всех фиксированных значениях числа вершин и диаметра графа-дерева экстремальное  дерево является единственным с точностью до изоморфизма.

Для задачи о кратчайшем пути в условиях неопределенности развит новый подход и построена оригинальная модель учета вероятностной неопределенности. Ключевой особенностью предлагаемой модели является то, что вместо основанных на моментах множеств неоднозначности, которые явно учитывают моменты первого и второго порядка, используются стандартизированные множества неоднозначности. Эта предпосылка позволяет построить множества неоднозначности из частично наблюдаемых и ненадежных данных. Показано, что вероятностные ограничения могут быть усилены с помощью новой доступной информации и, следовательно, могут быть адаптированы к последовательному процессу принятия решений. Представленные теоретические и численные результаты демонстрируют преимущества предлагаемого подхода по сравнению со стандартными робастными и робастно-стохастическими методами оптимизации. Показано, что качество робастно-стохастических решений зависит как от качества собираемой информации, так и от структуры вероятностных ограничений. В частности, при соответствующем выборе параметров робастно-стохастические решения могут обеспечить разумную аппроксимацию оптимального решения в условиях полной информации.

По третьему направлению исследований рассматривались задачи маршрутизации транспортных средств с разделенными поставками в неоднородном парке с ограничениями клиентов на транспортные средства. Развито два новых подхода для решения задач с жёсткими ограничениями. Первый подход использует идею  «сначала кластеризация - затем построение маршрутов». Второй подход заключается в определении выполнимости каждого назначения заказа на транспортное средство при построении решения в конструктивных эвристических и точных алгоритмах. Предложен оригинальный эффективный алгоритм решения задач.  В этом алгоритме мы считаем, что все клиенты сортируются по их классам (типам) так, что сначала клиенты принадлежат к классу с наименьшим набором транспортных средств, затем идут клиенты с более широким набором транспортных средств и так далее. Клиенты одного и того же класса могут быть отсортированы в порядке убывания их требований. Точно так же транспортные средства сортируются, начиная с самого маленького набора транспортных средств, и внутри каждого набора транспортные средства сортируются в порядке возрастания их стоимости. Показано, что предложенный алгоритм гарантирует получение качественных решений в самых сложных задачах маршрутизации транспортных средств из рассматриваемого класса, возникающих в реальных приложениях, для которых традиционные подходы не могут найти даже допустимых решений.

По четвертому направлению исследований методы и подходы, развитые в проекте, были применены к анализу данных фондовых рынков. Были рассмотрены сетевые модели рынков различных стран за различные периоды и исследована устойчивость алгоритмов идентификации основных характеристик сети. Рассматривались две модели рыночной сети. Первая модель основана на классической корреляции Пирсона как меры связи между доходностями акций. Вторая модель основана на мере сходства знаков доходностей акций. Устойчивость процедур идентификации исследована для следующих характеристик рыночной сети: распределение весов ребер, распределение степеней вершин в графе рынка, клики и независимые множества графа рынка, и распределение степеней вершин максимального остовного дерева. Показано, что статистические процедуры идентификации, основанные на подобии знаков, обладают свойством устойчивости, в отличие от процедур, основанных на классической корреляции Пирсона.

Степень внедрения, рекомендации по внедрению или итоги внедрения результатов НИР

Полученные результаты могут быть использованы при анализе фондовых рынков (методы сетевого анализа рынков), в биоинформатике (анализ сетей экспрессий генов), в теории и практике принятия решений (принятие решений в условиях неопределенности), в практических задачах транспортной логистики (задача распределения транспорта). 

Публикации по проекту:


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
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. 2020. P. 1-29. 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. 
Savchenko V. V., Savchenko A. Method for Measuring Distortions in Speech Signals during Transmission over a Communication Channel to a Biometric Identification System // Измерительная техника. 2021. Vol. 63. No. 11. P. 917-925. doi
Semenov D., Koldanov A. P., Koldanov P., Pardalos P. M. A robustness comparison of two market network models // IMA Journal Management Mathematics. 2021. P. 1-15. doi