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

Почта: drobyshevsky@ispras.ru

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

(мест нет)

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

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

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

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

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

(мест нет)

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

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

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

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

Ключевые слова: машинное обучение (machine learning), модели случайных графов (random graphs), вложение графов (graph embedding)

Публикации:

 

 

ТЕМЫ РАБОТ ДЛЯ СТУДЕНТОВ

На 2019/20 конкретных тем пока нет, для ориентира можно посмотреть темы прошлых лет по теме случайных графов.

 

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

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. см. страницу Гомзина Андрея

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