Дробышевский Михаил Дмитриевич

Контакты: drobyshevsky@ispras.ru

Образование: ФУПМ МФТИ — бакалавриат (2013), магистратура (2015), аспирантура (2019); к.ф.-м.н. (2019)

Научные интересы:

  • машинное обучение (machine learning), сложные сети (complex networks), модели случайных графов (random graphs), вложение графов (graph embedding)
  • применение методов анализа сложных сетей в задачах биоинформатики

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

НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ

 

набор на 2022-2023 год не веду, все места заняты!

 

1. Алгоритмы краулинга графов

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

Общая постановка задачи — собрать максимально полный сэмпл графа с заданными свойствами при ограниченном бюджете. Например, требуется получить не менее 90% вершин графа ВКонтакте со степенью больше 1000 за минимальное количество API запросов.
При этом есть вариации:

  • граф может быть
    • static/dynamic (меняется пока мы собираем)
    • unobserved/partially observed
    • directed/undirected
  • свойством может быть степень вершины, ее значимость и т.п.
  • собрать хотим максимум вершин или ребер
  • ограничен бюджет, хотим собрать максимум вершин или есть целевой % вершин, минимизируем запросы
  • сколько получаем за один запрос — всех или k соседей
  • соседи вершины скрыты (закрытый профиль) — тогда о ней можно понять по ее известным соседям

Параллельная цель — привлечь математический аппарат сложных сетей для обоснования работы алгоритмов краулинга, теоретических оценок их свойств.

 2. Модели случайных графов

В реальном мире многие данные имеют графовую структуру: социальные сети (Фейсбук, Твиттер), Интернет, графы цитирований, метаболические сети, нейронные сети, автономные системы и т. д. Часто графы обладают нетривиальными топологическими свой­ствами — например, известная теория 6 рукопожатий —  и поэтому называются сложными сетями.

Насколько надежна сеть Интернет? Как устроены общественные отношения,отраженные в социальных сетях? Какие законы управляют распространени­ем болезней и информационными потоками и как ими можно управлять? Для поиска ответов на подобные вопросы активно разрабатываются математические модели случайных графов. Они являются попыткой угадать настоящие механизмы формирования структуры сетей; например, принцип предпочтительного присоединения, по-простому “богатый становится богаче”, успешно объясняет свойство безмасштабности, наблюдаемое почти во всех реальных сетях.

Кроме объяснения свойств, случайные графы применяются для анонимизации данных (как опубликовать граф Фейсбука, не нарушив приватность информации пользователей?), создания синтетических датасетов (как надежно протестировать свой алгоритм на графе если доступен только один-два реальных графа?) и др.

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

3. Применение анализа графов в биоинформатике

(пока в разработке)

Публикации:

профиль на GoogleScholar

 

ТЕМЫ ПРОШЛЫХ ЛЕТ

8. Исследование алгоритма сбора влиятельных вершин в социальных графах [Айвазов Д.А. 2019-20]

Из текста диплома Айвазова Д.А.:

«Социальные сети получили очень широкое распространение и объединяют мил­лиарды пользователей. Но с усложнением сети растёт и интерес к её исследованию и разнообразие информации, которую можно из неё извлечь. По сети друзей чело­века можно описать законы поведения и различные социальные явления, изучить влияние лидеров мнений, оценить скорость распространения информации, увидеть динамику изменения и развития дружеских связей и многое другое [1]. Для изуче­ния социальной сети удобно представлять её в виде графа — множества из вершин (аккаунтов пользователей сети) и рёбер, их соединяющих. Рёбра в данном случае отражают связи: дружба, подписка и т.д. Такую модель удобно исследовать, изучая свойства отдельных вершин, их распределение и метрики самого графа. Это позволя­ет создавать математическую модель, с похожими свойствами, с помощью которой можно изучать реальный граф и предсказывать его развитие [2]. Самые популярные социальные сети: Facebook, Instagram, Twitter и другие до­стигают размеров в миллионы, и даже миллиарды аккаунтов, и их скачивание и полный анализ довольно трудоёмкий процесс. Но кроме размера социальной сети на пути исследователей встаёт ещё одна проблема: искусственное ограничение на число запросов к серверам через API — Application Programming Interface, которое устанав­ливает каждая социальная сеть на своё усмотрение, чтобы не нагружать хранилища и не дать собрать всё целиком [3]. В сборе социальных сетей (social network crawling) вычислительная сложность алгоритмов не является ограничением и главной пробле­мой остаётся число запросов к серверу. С помощью специальных сборщиков данных — краулеров (crawler), становится возможно за ограниченный бюджет запросов собрать выборку меньшего размера и исследовать уже её, потому что из всего графа прежде всего интересны вершины с наилучшими показателями каких-то метрик центральности — влиятельные пользова­тели [4]. Они влияют на скорость распространения информации, на других пользо­вателей, соединяют слабо связанные части графа и т.д. Целью данной дипломной работы является сравнение алгоритмов краулинга вер­шин с наибольшими значениями важных мер центральности в социальных графах. В процессе работы была написана и опубликована статья [5] со сравнением основных решений в этой области, а данная дипломная работа является её расширением.»

Литература:

  1. Catanese S. A., De Meo P., Ferrara E. et al. Crawling facebook for social network analysis purposes // Proceedings of the international conference on web intelligence, mining and semantics. 2011. P. 1-8.
  2. Newman M. E. The structure and function of complex networks // SIAM review. 2003. Vol. 45, no. 2. P. 167-256.
  3. Ye S., Lang J., Wu F. Crawling online social graphs // 2010 12th International Asia­-Pacific Web Conference / IEEE. 2010. P. 236-242.
  4. Freeman L. C. Centrality in social networks conceptual clarification // Social net­works. 1978. Vol. 1, no. 3. P. 215-239.
  5. Drobyshevskiy M., Aivazov D., Turdakov D. et al. Collecting Inѕuencers: A Compar­ative Study of Online Network Crawlers // 2019 Ivannikov Ispras Open Conference(ISPRAS) / IEEE. 2019. P. 42-48

 

7. Разработка эффективного алгоритма поиска влиятельных пользователей в социальном графе [Шайхелисламов Д.С. 2019-20]

Из текста диплома Шайхелисламова Д.С.:

«Стремительный рост популярности социальных сетей, таких как Twitter, Facebook, привлекает внимание исследователей из самых разных областей. Благодаря изуче­нию этих сетей становится возможным получить глубокое представление о челове­ческом поведении в масштабах общества, например, понять, как формируются соци­альные группы, распространяется информация или болезнь, возникают или исчезают дружеские связи.
В любом анализе сети, как правило, доминируют постоянные пользователи, т.к. остальные не отличаются высокой активностью или высоким уровнем связности совсей сетью – имеют мало подписчиков или «твитят» всего несколько раз в месяц. Следовательно, для проведения анализа нет необходимости в сборе всего графа, до­статочно лишь его репрезентативной выборки [1].
Известно, что, по сравнению с обычными пользователями, пользователи влия­тельные [2] в социальных графах играют более важную роль с точки зрения связ­ности, влияния и распространения информации. В связи с этим анализ структуры связности и информационного обмена внутри только лишь «влиятельной» части се­ти, содержащей всех влиятельных пользователей и их попарные отношения, обеща­ет ряд интересных возможностей. Во-первых, такие пользователи обычно являются широко известными личностями (знаменитости, политики) или представляют собой целые организации (информационные агентства, технологические компании) с опре­деленными социальными, культурными или географическими атрибутами, которые могут быть использованы для анализа шаблонов отношений между элитными пользо­вателями. Во-вторых, поскольку влиятельные пользователи в совокупности, как пра­вило, связаны со значительным числом постоянных пользователей социальной сети, анализ таких взаимоотношений может дать ценную информацию об общей структуре всей сети.
Основываясь на этих наблюдениях, репрезентативную выборку можно сформи­ровать из множества влиятельных узлов. Влиятельность узла может быть опреде­лена как мера его центральности в графе. В данной работе влиятельными будем считать узлы с большой степенью. Можно предположить, что люди с большим чис­лом подписчиков или друзей в социальной сети – это лидеры мнений.
Стоит отметить, что сбор данных может быть сложной задачей, поскольку неко­торые сети, особенно социальные, скрыты в целях сохранения конфиденциальной информации. Впрочем, они предоставляют удобный и доступный канал сбора – API. Стоит также учитывать, что при обработке запросов по API пользователь может столкнуться с такими проблемами, как ограниченность по времени или по количе­ству запросов; потребность в огромном количестве ресурсов для хранения и анализа больших реальных графов.
Предполагается, что сети имеют ограниченный доступ к сетевым данным, од­нако поддерживают алгоритмы обхода. В начале обхода возможен доступ к произ­вольному узлу или конечному множеству узлов в сети. Алгоритм посещает вершину, выполняя запрос по API или веб-скрапинг. Для простоты положим, что каждый узел имеет унитарную стоимость, т.е. один шаг работы алгоритма равен одному запросу. В свою очередь на запрос возвращается полный список соседей вершины. По мере продвижения по графу, наблюдаемая часть сети расширяется, а видимые вершины могут быть сгруппированы на две категории (рис. 1): посещенные (скрауленные) и наблюдаемые. Хороший алгоритм сбора, (далее – краулер), должен максимизировать долю влиятельных узлов среди всех собранных при ограниченном числе запросов.»

Литература:

  1. Ahmed N. K., Neville J., Kompella R. Network sampling: From static to streaming graphs // ACM Transactions on Knowledge Discovery from Data (TKDD). 2013.Vol. 8, no.
    2. P. 1–56.
  2. Al-Garadi M. A., Varathan K. D., Ravana S. D. et al. Analysis of online social network connections for identification of influential users: Survey and open research issues // ACM Computing Surveys (CSUR). 2018. Vol. 51, no. 1. P. 1–37.

 

6. Оптимизация процесса генерации ребер графа в модели ERGG (Embedding-based Random Graph Generator) [Портной А.М. 2019-20]

Аннотация: «В данной работе исследуется генератор графов, похожих на данный, ERGG (Embedding-based Random Graph Generator) и предлагается модификация процесса генерации ребер в данном генераторе для более быстрой его работы. Проводится экспериментальное сравнение предложенной модификации на графах различного размера из различных доменов. Предложенная модификация позволяет существенно сократить время генерации ребер в генераторе ERGG.»

5. Исследование свойств динамических графов [Портной А.М. 2018-19]

Некоторые графы реального мира со временем увеличиваются в размерах (социальные сети, графы цитирований и т.п.), при этом динамика изменения их характеристик мало изучена. Известно, например, что кол-во ребер от кол-ва вершин зависит по степенному закону [1], а начиная с какого-то момента роста графа (gelling point), его диаметр начинает уменьшаться [2]. На практике возникают вопросы прогнозирования будущей структуры графа, например: насколько хорошо будет работать Интернет-протокол через пять лет? какие свойства будет иметь граф Facebook когда кол-во пользователей вырастет?

Выяснив динамику различных метрик в реальных данных, нужно проверить существующие модели случайных графов на способность воспроизведения такого поведения в сгенерированных графах. Например, распределение подграфов размера 3 позволяет классифицировать графы по доменам [3,4], и есть предположение, что этот признак меняется слабо с ростом графа. Интересно разработать модель, автоматически выявляющую закономерности по серии снэпшотов графа увеличивающегося размера, и способную таким образом предсказать будущее состояние данного графа.

Задачи:

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

Литература:

  1. J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 1, no. 1, p. 2, 2007.
  2. M. McGlohon, L. Akoglu, and C. Faloutsos, “Weighted graphs and disconnected components: patterns and a generator,” in Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008, pp. 524–532.
  3. Comparing predictive powers of Network Motif Distribution and structure of Overlapping Communities
  4. Mining Large Networks with Subgraph Counting (section 4.2)

 

4. Вычисление модулярности для направленных взвешенных графов с пересекающимися сообществами [Зимнюков М. 2018-19]

Один из способов оценить качество работы метода поиска сообществ в графе, не имея правильного ответа (ground truth) — измерение модулярности [1]. Основная проблема в том, что существующие алогритмы имеют сложность квадратичную и более от размера графа, что делает их почти неприменимыми для графов с более 100К вершин. Специфику задаче придают следующие аспекты: направленные ребра, веса на ребрах, пересекающиеся сообщества. Формула для модулярности, учитывающая все три аспекта, была предложена в [2]. Предлагается расширение работы [2], а именно:

  • реализовать быструю версию алгоритма расчета модулярности (например на C++)
  • провести больше экспериментов на графах из различных доменов
  • (дополнительно) адаптировать алгоритм поиска сообществ как оптимизацию модулярности, подобно [3]
  • (дополнительно) опубликовать статью по результатам

Литература:

  1. https://en.wikipedia.org/wiki/Modularity_(networks)
  2. Параллельное вычисление модулярности для направленных взвешенных графов с пересекающимися сообществами
  3. Fast unfolding of communities in large networks

 

3. Сравнение методов генерации графов, похожих на данный [Бардуков А. 2018-19]

Задача сгенерировать граф, похожий на данный, возникает, например, когда необходимо опубликовать граф, не раскрывая конфиденциальную информацию. Например, для анализа социальной сети Вконтакте исследователям нужна структура всего графа, однако связи между конкретными пользователями не должны быть раскрыты. Наивный метод анонимизации путем замены id всех пользователей на случайные не гарантирует защиты [1]. Существуют различные виды атак, использующие встраивание искусственных узлов-пользователей в граф с заранее известной конфигурацией связей для «узнавания» ее после анонимизации и прочие [2]. Поэтому цель — генерация графа, похожего на данный в смысле графовых метрик, но при этом достаточно отличающийся от него, чтобы скрыть конфиденциальную информацию (обзор методов в [3]).

Другая область применения — создание искусственных датасетов для тестирования алгоритмов на графах. Часто в наличии есть граф в одном экземпляре или только его часть (сэмпл сети Вконтакте), а работу нового алгоритма (например, приближенный подсчет диаметра) необходимо проверить на разных графах. Для этого генерируется выборка похожих случайных графов с некоторым разбросом в основных характеристиках и на ней тестируется статистическая значимость результатов вычисления, времени работы алгоритма, его масштабируемости и т.д. См. Обучение и масштабирование сетей на основе вложения графа.

Отталкиваясь от результатов статьи Reproducing Network Structure: A Comparative Study of Random Graph Generators, предлагается исследовать существующие модели-генераторы случайных графов в контескте описанных приложений.

Литература:

  1. L. Backstrom, C. Dwork, and J. Kleinberg, “Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography,” in Proceedings of the 16th international conference on World Wide Web. ACM, 2007, pp. 181–190.
  2. A. Narayanan and V. Shmatikov, “De-anonymizing social networks,” in Security and Privacy, 2009 30th IEEE Symposium on. IEEE, 2009, pp. 173–187.
  3. S. Ji, W. Li, P. Mittal, X. Hu, and R. A. Beyah, “Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization.” in USENIX Security Symposium, 2015, pp. 303–318.

 

Блокчейн, смартконтракты, распределенные приложения

Одна из целей проекта ColorChain разработка инструментов создания смарт-контрактов для разработчиков распределенных приложений (dApps). Необходимо будет анализировать как работают разнообразные платформ на основе блокчейн технологии, такие как Ethereum, Hyperledger, NEO и многие другие. В частности придется разбираться с экосистемой, алгоритмами консенсуса, виртуальной машиной (скорее всего Java).

Литература:

  1. Изучаем блокчейн на практике
  2. 20 областей применения Блокчейн вне финансовых сервисов
  3. Blockchains don’t scale. Not today, at least. But there’s hope Проблема масштабируемости и варианты ее решения
  4. Обзор альтернатив Proof of Work. Часть 1 Часть 2
  5. Ethereum-блокчейн и его использование на практике
  6. Техническая документация Telegram Open Network в частности 2.8 — обзор blockchain проектов

ФинТех

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

На данный момент едва ли существуют стратегии более успешные, чем классическая «buy and hold» на большом промежутке времени. Однако применение методов машинного обучения для предсказания поведения котировок может дать результат лучше, чем в среднем по рынку.

В этой теме у нас задела еще не имеется, поэтому предлагаются следующие направления исследований:

  • создание инструмента для анализа и тестирования торговых стратегий на исторических данных
  • разработка алгоритма обучения с подкреплением для оптимизации прибыли

Ключевые слова: автоматизированная торговля (algorithmic trading), обучение с подкреплением (reinforcement learning)

2. Исследование и разработка методов вычисления распределения подграфов в графе — Methods for Subgraph Distribution Computing in a Graph [Портной А.М. 2017-18]

Традиционно для описания свойств таких графов используют множество статистик: распределение степеней вершин, коэффициент кластеризации, собственные значения матрицы смежности и многие другие. Одной из интересных характеристик графа является распределение подграфов малого размера. Например, распределение подграфов размера 3 и 4 в графе [1] позволяет классифицировать графы из различных доменов (социальные сети, биоинформатика, графы цитирования и т.д.) с большей точностью, чем это позволяют сделать другие признаки [2,3]. Вычисление распределения подграфов в ориентированном графе довольно сложно даже для подграфов размера 3. Для этого было разработано несколько инструментов, в том числе использующих приближенные алгоритмы.

В работе предлагается:

  • провести обзор существующих инструментов
  • выяснить, необходимо ли разработать новый (распределенный, более точный/быстрый и т.п.) алгоритм подсчета подграфов
  • реализовать придуманный алгоритм

Быстрые алгоритмы:

  • gtrie (the fastest, but consumes a lot of memory)
  • Arabesque (needs hadoop, undirected graphs only).

Приближенные алгоритмы:

  • mfinder (very slow, dislike duplicate edges and loops)
  • FANMOD (only GUI, slow)
  • FaSE analogue to gtrie (fast, but fails on > 1M graphs)
  • FASCIA very cool but undirected only

Другие инструменты:

Литература:

  1. Random Graphs with Motifs
  2. Comparing predictive powers of Network Motif Distribution and structure of Overlapping Communities
  3. Mining Large Networks with Subgraph Counting (section 4.2)
  4. Learning multifractal structure in large networks (section 6.2)
  5. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs

Результат: диплом

 

1. Использование распределения подграфов в графе для определения демографических атрибутов пользователей сети Интернет [Ефремова М.А. 2017-18]

Среди предложенных тем для студентов есть задача Определения демографических атрибутов пользователей сети Интернет по текстам их сообщений [1]. В качестве признаков для предсказания используются тексты публичных сообщений пользователей и другие открытые данные. Предлагается рассмотреть как новый признак распределение подграфов размера 3 в графовой окрестности пользователя в социальном графе: т.е. графе, состоящем из его друзей (1-я окрестность) или друзей всех друзей (2-я окрестность).

Задачи:

  • добавить распределение подграфов в качестве признака для некоторого алгоритма предсказания атрибутов
  • выяснить, как новый признак влияет на качество предсказания, в т.ч. размер окрестности, размер подграфов (3, 4), попробовать также неориентированные подграфы

Литература:

  1. см. страницу Гомзина Андрея

Результат: диплом