Случайные графы для анализа социальных и информационных сетей и алгоритмы, основанные на Марковских цепях

Исследование направлено на изучение асимптотических свойств случайных графов и создание для них различных алгоритмов, построенных на основе Марковских цепей и статистической физики.Изучение свойств и создание алгоритмов для случайных графов помогает моделировать сетевые процессы, такие как образование сообществ, распространение информации, болезней и т.д., происходящие в реальных графах.В проекте делается упор на задачу выделения сообществ и исследования асимптотических кластерных свойств графов. Среди алгоритмов рассматриваются те, которые используют только локальную структуру графа. Вычисления в таких алгоритмах могут быть эффективно распределены. Такой подход позволяет существенно сократить необходимое время его работы и повысить эффективность. Отдельной задачей проекта является теоретическая оценка качества и скорости работы таких алгоритмов для определенных моделей случайных графов.