С тех пор как Аристотель заложил основы естественной систематики, классификация и категоризация играют центральную роль в философских и научных исследованиях по организации знаний. Чтобы идти в ногу с большим количеством информации, которую мы собираем в науке, ученые исследовали различные способы автоматической классификации данных еще на заре компьютерной и информационной наук.
Сейчас мы живем в эпоху больших данных и, к счастью, у нас есть несколько инструментов для классификации данных из различных источников, включая облака точек, изображения, текстовые документы и сети. Сети узлов и связей представляют собой простые, но мощные представления наборов взаимодействий данных из большого числа различных источников. Метаболические пути, белково-белковые взаимодействия, регуляция генов, пищевые сети, всемирная паутина, социальные взаимодействия и научное сотрудничество — вот лишь несколько примеров сетевых систем, изучаемых в разных науках.
Многие сети в реальной жизни настолько велики, что мы должны упростить их структуру, прежде чем сможем извлечь полезную информацию о системах, которые они представляют. В этой статье мы сосредоточимся на классификации узлов в сообщества и на визуализации структуры сообщества. В сетях сообщества относятся к группам узлов, которые тесно связаны внутри.
Обнаружение сообществ в сетях является сложной задачей, и в последние несколько лет было предложено множество алгоритмов для решения этой сложной проблемы. Текущая реализация Infomap быстра и точна. Infomap может классифицировать миллионы узлов за считанные секунды. Кроме того, структура уравнений карты также гибка и может быть прямо обобщена для анализа различных видов сетевых данных. Например, Infomap не только предоставляет двухуровневые, многоуровневые и перекрывающиеся решения для анализа неориентированных, направленных, невзвешенных и взвешенных графов, но и также для анализа сетей, содержащих данные более высокого порядка, таких как сети памяти и мультиплексные сети.
mapequation.org — сайт, посвященный алгоритму Infomap и его модификациям, от авторов метода. Есть открытый код. Помимо хорошей поддержки и документации, есть изумительные демки, иллюстрирующие работу. Визуализированные примеры работы алгоритма на основе случайного блуждания в многослойной сети можно изучить по ссылкам:
Также разработчики представляют онлайн сервис для визуализации, который работает локально на вашем компьютере и не выгружает данные ни на один сервер. Возьмем для примера готовый датасет, содержащий граф цитирования журналов, предоставленный ими же.
Из представленных скриншотов видно, как по мере приближения к узлу нам показывают из каких узлов он состоит.
Также Infomap доступен в виде библиотеки на python.
Установка:
Подключение:
Создание:
В параметрах можно передать флаги в виде строки.
Добавление узла:
Добавление именованных узлов в виде кортежа:
Добавление узлов многослойной сети:
Добавление связи:
Или сразу несколько передаем в кортеже:
Третьим параметром можно задать вес. Если при добавлении ссылки окажется, что узел не существует, он будет автоматически создан.
Для многослойной сети:
Запуск построения карты:
После этого можем извлекать из построенной карты необходимую информацию, например вывести количество верхних модулей в дереве:
Или вывести максимальную глубину дерева:
Созданную карту можно сохранять в файл и читать из него, удалять узлы и связи, работать с узлами состояний, потоками узла и многое другое.
Комментарий удален модератором