Ментор Алексей Николаевич Хлюпин — кандидат физико-математических наук, руководитель Лаборатории Неупорядоченных Систем (DisLab) ФПМИ, доцент, старший научный сотрудник МФТИ
Проект: Исследование стабильности алгоритмов поиска на графах с учетом случайной природы неопределенности информации В этом исследовательском проекте рассматривается устойчивость алгоритмов поиска в сложных сетях при работе с неполной информацией или неопределенностью. Мы предлагаем теоретическую модель для исследования того, может ли глобальный алгоритм поиска с неполной априорной информацией быть побежден стохастическим жадным поиском (в среднем по реализациям). Модель включает случайные переменные для возмущения весов ребер в графе, тем самым фиксируя неопределенность доступной информации.
Предварительные результаты показывают, что существуют некоторые графы и параметры модели неопределенности, где глобальный алгоритм поиска терпит неудачу в условиях неопределенности, в то время как случайный жадный поиск работает лучше. Необходимо развить и протестировать нашу предложенную модель с помощью численного моделирования на различных синтетических и реальных графах с различными структурами. Наши общие результаты смогут дать новое представление о разработке и оптимизации алгоритмов поиска для сетевых приложений, таких как сети связи, социальные сети и биологические сети. Мы также видим приложения наших исследований в других разнообразных областях: изучение памяти и ассоциативного обучения у миниатюрных насекомых, эффективные стратегии поиска и ходьбы для небольших роботов или устройств, работающих в ограниченной области пространства.
Кроме данной темы, есть еще ряд других тем, которые всегда можно со мной обсудить по почте или в телеграм @alekse_kh
Prior Global Search Stability on Finite Graphs with Uncertainty.
This research paper addresses the stability of search algorithms in complex networks when dealing with incomplete information or uncertainty. We propose a theoretical model to investigate whether a global search algorithm with incomplete prior information can be outperformed by a stochastic greedy search on average. The model incorporates random variables to perturb edge weights in the graph, thus capturing the uncertainty of available information. Our findings indicate that some graphs and uncertainty model parameters exist where the global search algorithm fails under uncertainty conditions, while the random greedy search performs better. We derive a critical curve that separates stable from unstable graphs for global search with incomplete information. Interestingly, the critical curve’s behavior changes from monotonic to bell-shaped depending on the uncertainty parameters.
We test our proposed model through numerical simulations on various synthetic and real-world graphs with different structures. Our results offer insights into the design and optimization of search algorithms for network-based applications, such as communication networks, social networks, and biological networks. We also discuss the study of memory and associative learning in miniature insects, highlighting the potential of efficient search and walking strategies for small robots or devices that operate in a limited area in space.