name: Модели сложных сетей и алгоритмы на графах
keyword_list: Модели сложных сетей методы вероятностной оптимизации выделение сообществ анализ графов
abstract: Объект исследования: Модели сложных сетей и алгоритмы на графах.
  Цель работы: Проанализировать свойства существующих моделей сложных сетей и разработать новые реалистичные модели с желаемыми количественными и топологическими свойствами. Применить методы, основанные на графах, к различным практическим задачам: выделение сообществ, оценка дат публикации веб-страниц, обнаружение влиятельных элементов в сложных сетях и поиск ближайших соседей на основе графов близости.
  Методы исследования, кроме используемых приборов и аппаратуры: Методы теории вероятностей; методы математического анализа; статистические методы.
  Достигнутые результаты:
  1. Новый класс моделей обобщенного предпочтительного присоединения и теоретические результаты, полученные для всего класса (распределение степеней вершин, локальный и глобальный коэффициенты кластеризации, корреляции степеней вершин).
  2. Утверждение о том, что глобальный коэффициент кластеризации стремится к нулю с ростом числа вершин для всех графов со степенным распределением степеней вершин с бесконечной дисперсией.
  3. Теоретический анализ модулярности для d-регулярных графов, модели предпочтительного присоединения и модели пространственного предпочтительного присоединения.
  4. Принцип предпочтительного размещения, который позволяет генерировать структуры со степенным распределением размеров кластеров, и анализ полученных структур. 
  5. Модель предпочтительного присоединения с устареванием и анализ ее свойств.
  6. Анализ алгоритмов выделения сообществ, основанных на максимизации правдоподобия, и новая модель ILFR для этой задачи. Системный анализ задачи выделения сообществ на основе распространения информации в графе и новые эффективные подходы для этой задачи.
  7. Теоретический анализ проблемы выбора подходящей функции качества для алгоритмов выделения сообществ.
  8. Новый алгоритм датирования веб-страниц, основанный на вероятностной оптимизации.
  9. Новый алгоритм для быстрого выделения вершин большой степени в сложных сетях.
  10. Теоретические гарантии для алгоритмов поиска ближайших соседей, основанных на графах близости.
  Новизна: Предложенные модели сложных сетей впервые позволили моделировать и объяснять ряд свойств реальных сетей: например, степенное распределение размеров кластеров и свойство устаревания. Все теоретические результаты, полученные в работе, являются новыми. В частности, теоретический анализ класса моделей обобщенного предпочтительного присоединения позволяет перенести полученные результаты как на уже известные, так и на новые модели, подходящие под заданные критерии. Предложенные алгоритмы обнаружения сообществ, датирования веб-страниц и выделения влиятельных вершин также являются новыми.
  Внедрение: Предложенные модели сложных сетей позволяют объяснять и прогнозировать свойства реальных сетей, что в свою очередь важно для ряда практических приложений в экспериментальной физике, биоинформатике, информационном поиске и так далее. Предложенные алгоритмы выделения сообществ могут быть полезны для сжатия и визуализации графов, для целевой рекламы, поиска похожих научных работ в сетях цитирования, и др. Помимо этого, в работе предлагаются алгоритмы датирования веб-страниц и выделения влиятельных вершин в сетях. Рассматриваемые в работе алгоритмы поиска ближайших соседей на основе графов используются практически во всех приложениях машинного обучения.
  Эффективность: На основе проведенного анализа разработаны алгоритмы, эффективность которых продемонстрирована в экспериментах на ряде наборов данных.
  Область применения: Предложенные методы и подходы могут применяться для анализа сложных сетей и алгоритмов на графах в различных областях: информационые системы, социальные сети, рекомендательные системы, экономика, биология,  медицина.
chairman_dissertation_council.name: Николай
chairman_dissertation_council.surname: Верещагин
chairman_dissertation_council.patronymic: Константинович
chairman_dissertation_council.position: Профессор
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: L-9806-2016
chairman_dissertation_council.scopus_author_id: 7005187259
chairman_dissertation_council.rinc_id: 54
chairman_dissertation_council.url: https://www.hse.ru/staff/vereshchagin
chairman_dissertation_council.orcid: 0000-0002-7386-979X
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Вадим
organization_supervisor.surname: Радаев
organization_supervisor.patronymic: Валерьевич
organization_supervisor.position: Первый проректор
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.02.EX
oecds.name: COMPUTER SCIENCE, THEORY & METHODS
speciality_codes.name: Математическое моделирование, численные методы и комплексы программ
speciality_codes.code: 05.13.18
protection_organization.short_name: НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ "ВЫСШАЯ ШКОЛА ЭКОНОМИКИ", НИУ "ВЫСШАЯ ШКОЛА ЭКОНОМИКИ", ВЫСШАЯ ШКОЛА ЭКОНОМИКИ, НИУ ВШЭ, ВШЭ
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ "ВЫСШАЯ ШКОЛА ЭКОНОМИКИ"
protection_organization.ogrn: 1027739630401
protection_organization.supervisor_name: НИКИТА
protection_organization.supervisor_surname: АНИСИМОВ
protection_organization.supervisor_patronymic: ЮРЬЕВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Правительство Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: МФТИ
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)"
author_organization.ogrn: 1027739386135
author_organization.supervisor_name: НИКОЛАЙ
author_organization.supervisor_surname: КУДРЯВЦЕВ
author_organization.supervisor_patronymic: НИКОЛАЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения