Анализ процессов, Графы

Graph mining. Обзор инструмента Infomap для графовой аналитики

Время прочтения: 4 мин.

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

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

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

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

https://www.mapequation.org/apps/Multiplex3D-sampling/index.html

https://www.mapequation.org/apps/Multiplex3D-short-version/index.html

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

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

Также Infomap доступен в виде библиотеки на python.

Установка:

pip install infomap
Подключение:
import infomap
Создание:
im = Infomap()

В параметрах можно передать флаги в виде строки.

Добавление узла:

im.add_node(1)

Добавление именованных узлов в виде кортежа:

nodes = (
    (1, "Node 1"),
    (2, "Node 2"),
    (3, "Node 3")
)
im.add_nodes(nodes)

Добавление узлов многослойной сети:

source_multilayer_node = (0, 1) # ID уровня, ID узла
target_multilayer_node = (1, 2) # ID уровня, ID узла
im.add_multilayer_link(source_multilayer_node, target_multilayer_node)

Добавление связи:

im.add_link(1, 2)
Или сразу несколько передаем в кортеже:
links = (
    (1, 2),
    (1, 3)
)
im.add_links(links)

Третьим параметром можно задать вес. Если при добавлении ссылки окажется, что узел не существует, он будет автоматически создан.

Для многослойной сети:

links = (
    ((0, 1), (1, 2)),
    ((0, 3), (1, 2))
)
im.add_multilayer_links(links)
Запуск построения карты:
im.run()

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

print(im.num_top_modules)

Или вывести максимальную глубину дерева:

print(im. max_depth)

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

Советуем почитать