Графовые методы анализа

1. Графовые методы анализа

ГРАФОВЫЕ МЕТОДЫ АНАЛИЗА

2.

С 2020 года в области машинного обучения появилось направление,
связанное с использованием графов - машинное обучение на графах
(Graph Machine Learning или GML) и графовые нейронные сети (graph
neural networks или GNNs).

3. Сетевой анализ

СЕТЕВОЙ АНАЛИЗ
— метод социологии для изучения сообществ,
основанный на математической теории графов.
Основа сетевого анализа, как ни логично, — сети, а
точнее — представление данных в виде сети. Сеть (тот
же граф) — это какое-то количество объектов и связь
между ними, следовательно она состоит из двух
важнейших элементов: узлы и ребра.

4. Преимущества сетевого анализа

ПРЕИМУЩЕСТВА СЕТЕВОГО АНАЛИЗА
• Возможность найти скрытые и неочевидные связи
между изучаемыми элементами
• Универсальность
• Сочетание наглядности и репрезентативности

5. Часть графа по персонажам «Недоросля»

ЧАСТЬ ГРАФА ПО ПЕРСОНАЖАМ «НЕДОРОСЛЯ»

6. Что такое граф?

ЧТО ТАКОЕ ГРАФ?
Граф, или сеть – это модель, состоящая из узлов и
связей между ними, или ребер.

7. Графы бывают:

ГРАФЫ БЫВАЮТ:
• ориентированные и неориентированные (связи-стрелочки vs
обычные связи)
• связные и несвязные (все узлы связаны vs есть узлы, которые
оторваны от основного графа).
• взвешенные
и невзвешенные (связи имеют некоторое
числовое значение или нет)

8. Пример

ПРИМЕР

9. Интернет

ИНТЕРНЕТ

10. Некоторые понятия

НЕКОТОРЫЕ ПОНЯТИЯ
Метрика – это результат
определенным способом.
измерений,
проведенных
Степень, или мощность узла (degree) – это количество его
связей.

11. Как определить важность узла?

КАК ОПРЕДЕЛИТЬ ВАЖНОСТЬ УЗЛА?
degree centrality: у кого больше связей, тот и важнее
closeness centrality: чем центральнее узел (т.е. чем короче путь
от него до всех остальных узлов), тем он важнее
betweenness centrality:
проходящих через узел
количество
кратчайших
путей,
eigencentrality: чем больше друзей у твоих друзей, тем ты
важнее

12. Какие именно данные нужны и как они хранятся?

КАКИЕ ИМЕННО ДАННЫЕ НУЖНЫ И КАК ОНИ
ХРАНЯТСЯ?
Самый простой формат представления сетей в понятном компьютеру
виде — это таблицы. Мы можем закодировать сеть в виде таблицы,
представив, что одна строка = одна связь. Самый простой формат
таблицы, который можно записывать и читать хоть в блокноте (но и в
excel тоже можно) — это формат вида CSV (comma separated values).

13. Пример

ПРИМЕР
строка CSV-файла для описания связи
Митрофанушкой может выглядеть так:
Простаковой
с
Госпожа Простакова,Митрофанушка,11
(11 — условный вес их связи, в данном случае — число
диалогов между персонажами на протяжении пьесы).

14. Другие форматы

ДРУГИЕ ФОРМАТЫ
• на
основе
языка
разметки
форматы GraphML и GEXF)
• в виде текстового файла (.gml)
XML
(например,

15. Gephi 

GEPHI
Gephi – программа
для
визуализации
графов.

16. Граф отношений в «игре престолов»

ГРАФ ОТНОШЕНИЙ В «ИГРЕ ПРЕСТОЛОВ»

17. Особенности визуализации в gephi

ОСОБЕННОСТИ ВИЗУАЛИЗАЦИИ В GEPHI
После загрузки в программу предварительно
обработанных данных, Gephi предполагает количество
узлов и ребер, исходя из подготовленного файла и
строит граф по умолчанию:

18.

19. Особенности визуализации в gephi

ОСОБЕННОСТИ ВИЗУАЛИЗАЦИИ В GEPHI
Чтобы сделать граф наглядным, а самое главное — понятным,
нужно будет настроить цвет и размер узлов, их расположение,
длину ребер и т. д.
Есть два варианта раскраски:
• разными цветами по одному из признаков (примеры таких признаков: пол;
принадлежность к группе, например «Купцы»; количество произнесенных за
пьесу слов);
• одним цветом, но будет отличаться его интенсивность и яркость: по
признакам «количество произнесенных слов» и «степень» (количество связей
этого узла), чем больше значение признака, тем ярче цвет.

20. Особенности визуализации в gephi

ОСОБЕННОСТИ ВИЗУАЛИЗАЦИИ В GEPHI
Следующий шаг — добавить графу ясности и включить
подписи узлов. Всё это решается укладкой. Изначально, весь
граф уложен случайным образом, все элементы расположены
хаотично. Но у Gephi есть несколько встроенных способов
укладки.

21. Промежуточный результат

ПРОМЕЖУТОЧНЫЙ РЕЗУЛЬТАТ

22. Особенности визуализации в gephi

ОСОБЕННОСТИ ВИЗУАЛИЗАЦИИ В GEPHI
• Последнее, из базовых функций — это размер узлов. Можно
задать единый размер для всех узлов или проранжировать
по какому-то признаку. Допустим, проранжировать по
количеству слов у персонажа.

23.

24. Пример

ПРИМЕР