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

Примером, вытекающим из пандемии COVID, является то, что все узнали о концепции отслеживания контактов. Этот процесс включает в себя сбор информации о том, с кем кто-то контактировал и с кем контактировали эти люди. По сути, создание социальной сети, где узлы представляют людей, а ребра представляют контакты. Это тот случай, когда отношения, кто с кем контактирует, находятся в центре внимания анализа больше, чем характеристики рассматриваемого человека. Анализ графов — это применение методов и алгоритмов графов для ответа на вопросы, связанные с отношениями между объектами данных.

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

В сериале будут затронуты такие темы, как:

  • Сходство узлов
  • Центральность узлов и краев
  • Найти путь
  • Обнаружение сообщества
  • Выборка
  • Графики и типы графиков
  • … и многое другое

Почему меня это должно волновать и на какие вопросы могут ответить графики?

Полное обсуждение аналитики графов может легко превратиться в целую книгу, см., например, замечательную работу Стэнли Вассермана и Кэтрин Фауст или статью уровня доктора философии по алгоритму графа или производительности. Тем не менее, полезно сначала взглянуть на вопросы, которые может решить графовая аналитика, и проигнорировать детали работы алгоритмов.

Алгоритмы графов помогают ответить на такие разнообразные вопросы, как:

  • Как распространяются болезни в обществе?
  • Как развиваются международные торговые пути?
  • Какие статьи являются наиболее важными в списке цитирования?
  • Какие члены являются излишними или незаменимыми в организации?
  • Основываясь на потоке информации, как может функционировать отдел, если определенные люди уйдут?
  • Как добраться из пункта А в пункт Б с наименьшими затратами — классическая задача коммивояжера

Основы диаграммы

В следующем блоге мы рассмотрим это более подробно, а пока вот несколько ключевых частей графика:

  • Узлы — это действующие лица данных, также называемые вершинами в теории графов.
  • Ребра указывают на взаимодействия между узлами, также называемые ссылками.
  • Атрибуты — это характеристики узлов и ребер, иногда называемые функциями или свойствами.

Давайте рассмотрим следующий очень простой граф, состоящий из двух узлов, A и B, и одного ребра с атрибутом веса 3.

Введение в RAPIDS cuGraph за 3 простых шага

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

Для использования cuGraph требуется всего три шага: (1) загрузить данные графика; (2) создать график; и (3) вызвать алгоритм.

Хорошо, действительно четыре шага, так как пакеты должны быть импортированы.

Давайте углубимся в проблему

Учитывая набор социальных данных, мы хотим задать и понять вопрос: кто самый популярный и наименее популярный человек?

Рассмотрим простой набор данных, полученный в результате работы Дж. Л. Морено в 1940-х годах, когда он рассматривал партнеров за обеденным столом в общежитии в учебном заведении штата Нью-Йорк. Он собрал данные, спросив у всех двадцати шести девушек в общежитии их первых и вторых партнеров по обеду. Структура необработанных данных очень проста. Ответ каждого жителя представляет собой строку в файле, разделенном запятыми. «Источник» — это актер, отвечающий на вопрос, «цель» — это актер, с которым они хотели бы пообедать, а вес — либо 1 для первого выбора, либо 2 для второго выбора. Из примера данных, показанного ниже, вы можете видеть, что Ада предпочла бы сидеть с Корой в качестве первого выбора и с Луизой в качестве второго варианта. В левом верхнем углу рисунка 1 ниже мы видим ребра от Ады до Коры и Луизы с соответствующими атрибутами ребра.

Чтобы определить, кто является наиболее важным, мы рассмотрим пять различных показателей центральности:

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

Как и ожидалось, и Ева, и Марион превзошли все показатели. Следующий вопрос, который нужно задать: Чем различаются их роли?

Оценки промежуточности и PageRank предполагают, что Ева наиболее важна для линий связи и социальной структуры общежития. Оценки собственного вектора и Каца показывают, что Марион имеет наибольшее влияние как на популярных студентов, так и на все население.

И наоборот, самые низкие показатели по этим показателям также представляют интерес.

Многие жители имеют низкую связанность, как показано на диаграмме распределения степени, рис. 6 ниже. В общей сложности 10 из 26 студентов были выбраны в качестве предпочтительных партнеров только один раз или ни разу. Пул потенциально изолированных жителей составляет более трети населения.

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

Примечание: из-за небольшого размера набора данных степень центральности не полностью коррелирует с самой низкой степенью.

Помимо популярности, мы можем задать ряд дополнительных вопросов, например:

  • Кто в общежитии является наиболее изолированным?
    . Судя по данным, многие учащиеся имеют самую низкую степень центральности, определяя Алису, Лауру, Эллу и Кору как наиболее изолированных.
  • Кто уязвим для запугивания?
    . Такие люди, как Бетти и Рут, у которых были самые низкие показатели PageRank и центральности собственного вектора, не имеют влияния и связей, чтобы обратиться к другим, если над ними запугивают.
  • Кто подвергнется риску, если население изменится?
    - Те, у кого низкий уровень, по сравнению с другими с низким уровнем, такими как Ада и Кора, могут внезапно стать очень изолированными, если кто-то из них покинет общежитие.
  • Чьи голоса недостаточно представлены в группе?
    - Лаура имеет минимум связей только со студентами с высокими связями. Кажется, что у нее нет группы сверстников, и она может быть сторонним наблюдателем во взаимно связанных группах. Ее степень центральности минимальна, но имеет среднее значение по показателям связности.

Хотя на приведенные выше вопросы можно ответить, наблюдая за этими мерами, дальнейший анализ этого набора данных может ответить на такие вопросы, как:

  • Чье удаление больше всего нарушило бы социальную структуру в общежитии?
  • Кто влияет на социальный статус в общежитии?
  • Кто возвысится в известности, если конкретный человек покинет общежитие?

Что происходит, когда набор данных становится больше?

Давайте посмотрим на более крупный набор данных, который содержит более 40 тысяч ребер и показан на рисунке 6 ниже. В таком масштабе становится практически невозможно визуально различить характеристики отдельных узлов. Представьте, как будет выглядеть граф с более чем миллионом ребер.

На рисунке изображена сеть связи по электронной почте из печально известного корпоративного скандала Enron в 1990-х годах. Для нашего анализа мы продублируем те же измерения из приведенного выше простого набора. Однако мы должны полагаться на некоторые дополнительные внешние данные обогащения, чтобы увидеть, имеют ли ответы смысл.

Этот набор данных содержит метаданные электронной почты, опубликованные во время судебного разбирательства по делу о скандале с Enron.

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

  • Скандал имел широкий резонанс:
    - привел к банкротству Enron в 2001 г.
    - привел к судебным искам на миллиарды долларов, включая иск акционеров на 40 миллиардов долларов.
    - Артур Андерсон, в пятерке крупнейших бухгалтерская фирма была распущена.
    - Закон Сарбейнса-Оксли, среди прочих реформ, был принят для регулирования ведения финансовой отчетности.
    - Несколько сотрудников Enron были приговорены к тюремному заключению
  • Данные содержат 40777 уникальных почтовых подключений (ребер) между 6187 различными адресами электронной почты (узлами).
  • Веса, содержащие количество электронных писем между адресами, включены в данные о каждом соединении, но не используются в этом анализе. (Более поздние блоги будут использовать веса)

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

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

  • [email protected] связан с большинством участников графика.
  • [email protected] имеет самый высокий промежуточный и PageRank. Это электронное письмо является наиболее влиятельным в основной сети и наиболее важным для структуры графа. Это облегчает поиск кратчайших путей между другими узлами в графе.
  • [email protected] имеет самую высокую центральность собственного вектора. Этот узел оказал наибольшее влияние на весь граф, а не только на другие важные узлы.

Что делает cuGraph особенным?

Существует множество платформ и инструментов для графической аналитики, но cuGraph имеет целый ряд существенных преимуществ:

  • Для использования cuGraph не требуется никаких лицензионных сборов.
  • RAPIDS cuGraph интегрируется с широко используемыми пакетами с открытым исходным кодом, такими как DASK, PyTorch и scikit-learn.
  • Он является частью экосистемы ускоренного графического процессора RAPIDS с открытым исходным кодом, позволяющей начать ускорение графического процессора.
  • Широкая поддержка в сообществе RAPIDS и от NVIDIA через GitHub.
  • Это легко настроить. Эта статья не посвящена настройке/установке, но приведенные ниже ссылки содержат инструкции по запуску в нескольких средах.
  • Масштабируемость и производительность не имеют себе равных.
     – Один графический процессор емкостью 32 ГБ может обрабатывать до 250 миллионов ребер.
     – Инженеры NVIDIA протестировали cuGraph на нескольких узлах, Системы GPU на графах с более чем одним триллионом ребер.
  • Удобный интерфейс: существует API Python, аналогичный NetworkX, а для интеграторов есть API C и C++.
  • RAPIDS cuGraph доступен в Amazon AWS, Google CoLab и Paperspace.

Как начать работу с cuGraph.

Где найти дополнительную информацию о cuGraph.

RAPIDS cuGraph предоставляет полный набор документации и примеров, включая:

  • Прошлые блоги, презентации и официальные документы, связанные с cuGraph, здесь: https://docs.rapids.ai/api/cugraph/nightly/tutorials/cugraph_blogs/
  • Полная коллекция документации RAPIDS: https://docs.rapids.ai/
  • Тщательно протестированные и поддерживаемые блокноты cuGraph Jupyter: https://github.com/rapidsai/cugraph/tree/main/notebooks
    — Блокнот центральности, используемый для представленных здесь расчетов: https://github.com /rapidsai/cugraph/blob/main/notebooks/algorithms/centrality/Centrality.ipynb
     — записные книжки с примерами каждого поддерживаемого алгоритма.
     – некоторые включают масштабирование интеграции DASK для нескольких графических процессоров.
    - Все они обновлены с учетом последних дополнений и исправлений cuGraph.
    - Демонстрация визуализации, интеграции и сравнительного анализа алгоритма cuGraph.

В заключение

Как упоминалось во введении, это первая статья в серии блогов, посвященных анализу графов с использованием cuGraph. В следующем блоге будет рассмотрена концепция подобия, за которым последуют блоги о центральности, трансверсальности и других классах алгоритмов графов. В этой серии также будет рассмотрено понятие ETL графа и шаги, необходимые для обработки данных перед созданием графа. Наконец, серия будет включать новые актуальные темы и запросы, принятые в список проблем cuGraph GitHub по адресу https://github.com/rapidsai/cugraph/issues.

Дополнительные ссылки:

Дополнительную информацию об исследовании штата Нью-Йорк Обучение S Дж. Л. Морено можно найти в его книге Кто выживет по адресу: https://archive.org/details/whoshallsurviven00jlmo/mode/2up.

«Анализ социальных сетей: методы и приложения» Стэнли Вассермана и Кэтрин Фауст — замечательная книга.

Наконец, «Disrupting Dark Networks» Шона Эвертона — информативное чтение о применении сетевого анализа.

Лицензионный материал:

Изображение Enron взято с https://lucidmanager.org/data-science/analyse-enron-corpus и находится под лицензией Creative Commons Attribution-ShareAlike 4.0 International.