Как я придумал идею
Итак, я смотрел документальный фильм на Netflix, и они говорили о Джордже Буше-старшем. Буша и как он был директором Центральной разведки при президенте Форде и вице-президентом при Рональде Рейгане. Потом я подумал, что он тоже был президентом. Затем я вспомнил наших первых президентов и то, как Томас Джефферсон был госсекретарем Джорджа Вашингтона, а также вице-президентом Джона Адамса и самим президентом. Размышляя обо всех этих связях, я нарисовал в голове график и задался вопросом: насколько связаны наши политики?
Итак, я решил создать графовую сеть и задать несколько вопросов. Я также рассматривал это как возможность углубиться в науку о графических данных и узнать больше о том, как она может дать представление о связанных данных. Для первого раунда этого графика я буду загружать следующие позиции кабинета:
- Президент
- вице-президент
- государственный секретарь
- Министр обороны
- Секретарь внутренних дел
- Секретарь сельского хозяйства
- Генеральный прокурор
Я буду использовать Neo4j в качестве стека графических приложений. Для этого будут использоваться следующие приложения: Neo4j Desktop, Browser, Bloom, плагин Graph Data Science, Graph Data Science Playground, а также Microsoft Excel и Microsoft VSCode.
Какие вопросы задавать по данным?
У меня было несколько вопросов, которые я хотел задать графику, чтобы получить некоторое представление. Вот они:
- Могу ли я действительно найти путь, который связывает Джорджа Вашингтона и Джо Байдена?
- Существуют ли изолированные сообщества, где нет связи с основным графом?
- Какой президент самый влиятельный?
- Могу ли я порекомендовать человеку место в кабинете министров?
Модель данных
Первое, что я хотел сделать, это создать модель данных, которая обеспечила бы архитектуру моего графа. Вот пример того, как будет выглядеть график с некоторыми данными. В данном случае я использовал инструмент arrows.app. Этот инструмент действительно прост в использовании и позволяет довольно быстро построить схему. Я знал, что у меня будет один узел Person с отношениями между ними, представляющими должности (например, вице-президент, министр обороны и т. д.)
Сбор данных
Следующее, что мне нужно было сделать, это получить некоторые данные. Я решил сначала зайти в Википедию и посмотреть, что там есть. Одна приятная особенность данных в Википедии заключалась в том, что они уже были представлены в виде таблицы. Мне просто нужно было получить это в CSV для импорта.
Я мог бы использовать множество различных методов для сбора и очистки данных, таких как Python или R, но я выбрал Excel. Да, этот Excel… В Excel есть несколько отличных инструментов для извлечения данных из Интернета, извлечения таблиц, преобразования и очистки данных довольно легко и с минимальным кодом.
Сбор данных
Используя Excel, я указал ему на веб-страницу, и он может сканировать ее и извлекать найденные таблицы. Затем я могу преобразовать данные, удалить столбцы и т. д., чтобы подготовить их к дальнейшей очистке.
В главном меню Excel я перешел к данным, затем в разделе «Получить и преобразовать» на ленте, выбрал «Из Интернета», просто вставил URL-адрес и нажмите «ОК».
Затем Excel просканирует сайт и выведет список найденных таблиц. Я выбрал стол, на котором был список нужных мне людей.
Отсюда вы можете перейти к преобразованию данных и удалить столбцы (например, портрет) или нажать «Загрузить» и начать очистку в Excel. Я повторил это для всех других перечисленных мною должностей в кабинете министров.
Чистые данные
Теперь, когда данные загружаются из Интернета в Excel, мне необходимо выполнить некоторую очистку. Как мы видели на изображении выше, имя президента включает годы его рождения и смерти. В Excel есть две полезные функции, которые я использовал не только для извлечения имени, но и для очистки пробелов, новой строки и т. д.
'removes whitespace and newline
=TRIM(CLEAN(A1))
'pull text out before years since ( is start of char
=LEFT(A2, SEARCH("(",A2)-1)
Если вы не слишком хорошо знакомы с формулами Excel, попробуйте excelformulabot. Используя подсказку и GPT3, вы можете просто написать то, что вы ищете, и он создаст для этого функцию!
Я добавил новый столбец и запустил функцию LEFT, а затем запустил TRIM для этого нового столбца. Я также очистил другие столбцы, которые мне сейчас не нужны, и вот результаты:
Таким же образом я обработал остальные файлы и проверил, все ли в порядке. Теперь об импорте… на один шаг ближе к тому, чтобы увидеть мой график!
Создать базу данных и загрузить данные
Итак… с этим покончено… давайте создадим и загрузим базу данных!
У меня уже установлен Neo4j, поэтому в Neo4j Desktop я создал базу данных.
Как только он будет создан, мне нужно открыть следующее приложение, браузер Neo4j, чтобы я мог загрузить свой Cypher и импортировать CSV-файлы, которые я создал ранее.
Теперь я использовал Micrsoft VSCode для написания Cypher. Я мог бы использовать браузер Neo4j, но я привык к UX VSCode, и мне нравится IntelliSense, подсветка синтаксиса и универсальность.
После того, как я переместил файлы CSV в папку импорта db, я написал свой Cypher в VSCode, а затем скопировал/вставил в браузер, чтобы импортировать данные.
Вот это в браузере Neo4j
Как только он загрузился, я выполнил простой поиск по шифру для Джорджа Вашингтона….
MATCH (p:person) WHERE p.name =~ 'George Washington' RETURN p
…и вот он!
Теперь давайте посмотрим на его соединения... вы можете выбрать узел и нажать кнопку Показать отношения.
Видеть эту сеть действительно круто и отчасти открывает глаза. Просто глядя на отцов-основателей, было безумно видеть, насколько они были связаны.
Всякий раз, когда я вижу графики в реальной жизни, я всегда улыбаюсь, потому что у вас есть этот образ в голове, а затем, когда он создается, это большое достижение.
Давайте посмотрим, как это выглядит в Neo4j Bloom, и посмотрим, как растет сеть!
Это действительно здорово видеть, насколько они связаны. Вот изображение пары прошлых президентов, которые у нас были (Байден, Обама, Буш).
Наука о графических данных… наконец
Мы уже извлекли и очистили данные, а затем загрузили их в новую базу данных для некоторого визуального анализа. Итак, теперь давайте копнем глубже и посмотрим, какие еще идеи мы можем найти. У Neo4j есть отличная документация по алгоритмам Graph Data Science здесь.
Подводя итог, вот вопросы, которые я хотел задать:
- Могу ли я действительно найти путь, который связывает Джорджа Вашингтона и Джо Байдена?
- Существуют ли изолированные сообщества, где нет связи с основным графом?
- Какой президент самый влиятельный?
- Могу ли я порекомендовать человеку место в кабинете министров?
Теперь, чтобы ответить на эти вопросы, я рассмотрю несколько различных алгоритмов GDS.
Для # 1 я буду смотреть на алгоритмы поиска пути (естественно 😎)
Для № 2 я буду использовать алгоритмы обнаружения сообщества (здесь виден шаблон 🤔)
Для № 3 я рассмотрю несколько разных алгоритмов центральности.
Наконец, для № 4, как вы уже догадались…. Алгоритмы прогнозирования ссылок
Есть несколько разных способов запустить их в зависимости от вашего уровня комфорта с шифрованием. Вы можете вызвать библиотеку GDS в шифровании, создать свою проекцию (собственную или шифрованную) и передать свой график, параметры и т. д. Кроме того, Neo4j проделал большую работу по интеграции некоторых алгоритмов GDS в Bloom (их приложение для визуализации), поэтому он представляет собой гораздо более удобный способ взаимодействия с этими расширенными возможностями. В этом посте я буду использовать Bloom и его алгоритмы.
Кратчайший путь
Итак, первое, что нужно сделать, это найти и захватить мои начальные и конечные узлы (Джордж Вашингтон и Джо Байден).
Когда у меня есть узлы, я выбираю их оба, щелкаю правой кнопкой мыши по Джорджу и выбираю Shortest Path из контекстного меню.
Прежде чем я взгляну на результаты, я хотел разобраться, какой алгоритм он использует. Хотя это не задокументировано в Bloom, за кулисами он запускает Dijkstra Source-Target Shortest Path. Этот алгоритм работает на однородных графах, как направленных, так и неориентированных. Как следует из названия, он пытается найти кратчайший путь между двумя заданными узлами.
Я нашел хорошую анимацию и описание из Википедии здесь:
Иллюстрация алгоритма Дейкстры, находящего путь от начального узла (внизу слева, красный) к целевому узлу (вверху справа, зеленый) в задаче робот планирование движения. Открытые узлы представляют собой предварительный набор (также известный как набор непосещенных узлов). Закрашенные узлы — это посещенные узлы, цвет которых соответствует расстоянию: чем зеленее, тем ближе. Узлы во всех разных направлениях исследуются одинаково, появляясь более или менее в виде кругового волнового фронта, поскольку алгоритм Дейкстры использует эвристику, тождественно равную 0.
Итак, давайте пробежим кратчайший путь и посмотрим, что мы сможем найти!
Мы нашли путь!! (ну… вроде)
... и я имею в виду, что если вы посмотрите на узел, выделенный синим цветом, вы увидите, что он говорит: «Офис свободен». Итак, я удалил узел и повторно запустил алгоритм, но путь не был найден. Итак, хотя мне удалось найти путь, этот путь не был «чистым» путем людей, но, тем не менее, он показывал силу алгоритма. На следующем. . .
Сообщества
В следующей части я хотел исследовать, есть ли сообщества (группы узлов), которые присутствуют в моем графе. Эти алгоритмы помогают увидеть, есть ли узлы, которые отключены/подключены, где они кластеризуются, могут ли они развалиться и т. д. В этом случае алгоритм, который находится в Блуме, — это слабо связанные компоненты (WCC). С этого хорошо начать, чтобы увидеть, как выглядит ваш график, что связано, а что нет. В некоторых из этих алгоритмов есть некоторые параметры, которые повлияют на результаты.
Вот параметры:
Категории. На самом деле это относится к категориям ваших узлов. Итак, в моем случае это узел person, так как это однородный граф (узлы одного типа), но возможность его запуска на разных типах, если у вас гетерогенный граф, помогает нацелить ваш анализ.
Типы взаимосвязей. Это еще один способ ограничить анализ только определенными ребрами на графике. Так, например, мы можем сказать, что используем только отношение was_vp_for.
Ориентация: это относится к направлению отношений на вашем графике (если у вас есть ориентированный график). Существует три варианта: Естественный, Обратный и Ненаправленный. Для алгоритма WCC это не повлияло на мои результаты, но повлияет на другие алгоритмы, такие как степень центральности.
NATURAL(по умолчанию) соответствует вычислению исходящей степени каждого узла.REVERSEсоответствует вычислению степени входа каждого узла.UNDIRECTEDвычисляет и суммирует как степень исхода, так и степень входа каждого узла.
Стиль на основе правил. После запуска алгоритма Блум может применить к ним стиль в зависимости от сообщества, к которому они подключены.
Вот результаты моего анализа WCC.
Как мы видим, есть несколько разрозненных сообществ, в которых эти президенты не были частью более крупного политического графа. Вот эти президенты:
Президент Дональд Трамп
Президент Резерфорд Б. Хейс
Президенты Джеймс К. Полк, Джеймс Бьюкенен и Франклин Пирс
Президент Улисс С. Грант
Президент Вудро Вильсон
Как видим, на самом деле есть несколько «аутсайдеров», чей кабинет не входил в состав более крупного графа. Теперь я подумал, может быть, один или два, но, как показал анализ… их больше. Возможно, когда мы запустим алгоритмы центральности, мы сможем увидеть, есть ли узлы, которые являются ключом к сохранению целостности основного графа.
Влияние
Чтобы выяснить, кто является наиболее влиятельным, нам нужно сначала определить, что это означает по отношению к графовой сети. В моем случае у меня есть ориентированный граф, в котором ребра указывают на узлы. По мере создания этих соединений некоторые узлы будут иметь больше ребер, указывающих на них, чем другие. Если вы думаете об этом в контексте социальной сети, это ответ на вопрос «за кем больше всего следят?», «кто следит за большинством людей?» или «есть ли человек, связанный со многими людьми с большими связями?». В моем случае я буду использовать два разных алгоритма: центральность степени и центральность промежуточного положения.
Центральность степени
Здесь будут рассмотрены связи между узлами, а также ориентация отношений. Я собираюсь запустить как NATURAL, так и REVERSE, чтобы проверить влияние на графике, глядя на направленные отношения и их обратное.
Итак, используя Блум, я запустил степень центральности со всеми узлами, всеми отношениями и использовал направление отношений NATURAL, и вот результат.
По умолчанию стиль цветового градиента на основе правил использует последовательнуюцветовую шкалу. Теперь это не лучший способ показать разницу в данных, поэтому я собираюсь переключиться на расходящуюся шкалу, а также применить масштабирование размера к узлам на основе оценки центральности. Поскольку у Bloom нет стандартных цветовых рамп на выбор из коробки (см. запрос на улучшение здесь), я постарался сделать эту как можно ближе к цветовой шкале Inferno. Вы можете настроить минимальную, среднюю и максимальную точки, чтобы получить хорошее цветовое расхождение.
После применения вы можете легко увидеть, какие узлы имеют более высокую степень центральности, чем другие, и какой из них имеет самый высокий уровень. Когда я увеличиваю масштаб, мы видим, что это узел Office Vacant.
Итак, интересно, что Office Vacant был самым центральным при использовании NATURALориентации. Кажется, что на этом графике несколько президентов имели вакантные должности в одной точке, что было достаточно, чтобы придать этому узлу высокую центральность. К сожалению, Bloom не позволяет вам фактически увидеть результаты степени центральности в виде списка, поэтому я зашел на игровую площадку GDS, и вот 5 лучших результатов выполнения этого алгоритма:
Теперь вот в обратной ориентации (и визуально, и списком).
Как мы видим, использование расходящейся цветовой схемы помогает визуально идентифицировать узел с наивысшей центральностью. Когда мы увеличиваем масштаб, мы видим, что это президент Дональд Трамп.
Вот посмотрите на топ-5
Итак, Дональд Трамп имеет смысл, если подумать о том, сколько людей прошло через его кабинет за время его правления. Таким образом, больше связей = выше центральность.
Промежуточное положение
Это просмотрит мою сеть и найдет те узлы, которые действуют как «мост между кластерами». Будет интересно посмотреть, как это будет выглядеть на политическом графике, поскольку в нем будут люди, которые охватывают нескольких президентов и, таким образом, могут выступать в качестве «моста» между президентами.
Итак, похоже, что основатели-основатели были мостами внутри основного графика, что интересно, потому что, когда я впервые подумал об этом графике, именно они помогли сформировать график в моем сознании.
Прогноз связи
Теперь я собирался запустить некоторые алгоритмы прогнозирования ссылок на этом графике, чтобы спрогнозировать некоторые новые посты в кабинете, но концепция прогнозирования ссылок настолько обширна и детализирована (как и остальная часть GDS), что я не смогу отдать ей должное, поскольку подраздел. Кроме того, алгоритмы прогнозирования ссылок в Neo4j не включены в Bloom, а также в БЕТА-версию на момент написания, что потребует немного больше кода. Итак, я пока пропущу это и создам отдельный пост только о конвейерах Link Prediction.
Заключение
Как я упоминал ранее, Neo4j проделал хорошую работу, начав интегрировать некоторые алгоритмы GDS в Bloom. Bloom предоставляет богатую среду визуализации, позволяющую быстро увидеть результаты анализа без использования кода. Было бы неплохо увидеть больше интеграции с GDS в будущем. Единственным недостатком было то, что мне пришлось использовать 4 разных приложения для выполнения моего рабочего процесса. Neo4j недавно анонсировала новый продукт под названием Workspace (недоступный для пользователей настольных компьютеров), который в основном объединяет некоторые из этих приложений, к которым вы можете подписаться для получения раннего доступа. Я сохраню свои комментарии по этому поводу для другого поста.
Было довольно интересно увидеть некоторые из этих результатов на этом маленьком графике.
Результаты анализа WCC были довольно крутыми. Я не осознавал, сколько существует изолированных сообществ. Возможно, если я добавлю больше людей, эти сообщества присоединятся к большему графу или это создаст больше сообществ? Кроме того, мне было бы интересно покопаться в результатах запуска алгоритма обнаружения сообщества Лувена. Этот алгоритм копается в графе, чтобы оптимизировать модульность и найти наилучшую группировку узлов. Этот анализ действительно начал бы показывать существующие сообщества (могут ли эти сообщества быть сгруппированы по политическим партиям, пространственно или во времени?)
Этот анализ едва затрагивает глубину того, как далеко мы можем зайти в кроличью нору Graph Data Science. Одна вещь, которую я хочу сделать, это расширить график на все прошлые и настоящие позиции кабинета. Например, в начале я упомянул, что Джордж Буш-старший был директором Центральной разведки, но с 2005 года этой должности больше не существует. Ее заменил директор Национальной разведки. Вы также заметите, что первая запись для министра обороны была для президента Трумэна. Ранее он назывался военным министром. Кроме того, я думал о том, чтобы добавить людей из штата и, возможно, начать добавлять конгрессменов (начните со спикеров палаты, лидеров большинства / меньшинства, кнута и т. д.).
Все данные и шифры, использованные в этом посте, находятся в моем репозитории здесь.
Вот еще несколько ресурсов для более глубокого изучения Neo4j, GDS и т. д.
Платформа графических данных | Приложения и инструменты для графических данных | Neo4j
Демонстрации продуктов Neo4j (github.com)
Наука о графовых данных Neo4j | Графовые алгоритмы и машинное обучение | Графическая аналитика
