Пользователь
0,0
рейтинг
20 января 2012 в 02:33

Разработка → Gephi как средство визуализации данных

Так уж случилось, что я оказался ассистентом у профессора в университете. Никогда не думал, что прийдётся сталкиваться с оценкой рисков и визуализацией данных, будучи, по призванию, криптографом. Курс называется «Информационные сети» и включает в себя: анализ случайных процессов, моделирование малых миров; компьютерные алгоритмы для оценки свойств сети; экспериментальные исследования крупных сетей, а также анализ рисков, которые трудно предсказать.

В виду того, что курс читается в основном для ИТ-шников, лектор сделал ставку на то, чтобы дать достаточно теории с минимумом математики и большим количеством практики. Для большинства вышеупомянутых задач подходит программа NetLogo. Она включает собственный язык программирования высокого уровня, который позволяет с лёгкостью моделировать различные случайные процессы. Для визуализации разнообразных данных была выбрана программа Gephi.

На основе опыта использования последней и была написана статья, в которой рассматривается получение входных данных для ПО с последующей их визуализацией.

Собственно постановка задачи была таковой: визуализация каких-либо реальных данных средствами Gephi.



Генерация данных



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

Форматы файлов Gephi


Gephi понимает достаточно большое количество форматов файлов.

image

Как видно из рисунка, самый лучший вариант — использовать gexf. Как оказалось, это открытый формат и библиотеку с лёгкостью можно скачать с отсюда. На сайте пишется, что Libgexf в настоящее время работает только на Linux (проверено в Ubuntu 8.10 и 9.04). Не долго думая, решил скачать исходники и скомпилировать под Ubuntu 11.10 с интерфейсами для Python (так как остальную часть решил реализовывать на нём). Сгенерировал тестовый файл и решил запустить в Gephi, но с ее помощью не открылись ни мой файл, ни скачанные из интернета, ни даже тот, который сама сохранила. Не знаю что за баг, но, поковыряв немного и попробовав на двух машинах, решил от этой затеи отказаться и искать альтернативу. После того, как поигрался с CSV и понял, что его функционала мало, наткнулся на импорт из БД.

Его можно найти в «File -> Import Database -> Edge list ...». Сначала я думал, что «Edge list» это лишь импорт рёбер, но оказалось, что импортируются также и вершины. В качестве БД можно использовать SQLite, MySQL, PostgreSQL и Teradata. В окне импорта, сверху есть подсказка к параметрам таблиц. Должно быть две таблицы: nodes и edges. Таблица nodes должна содержать колонки:
  • обязательно:
    1. id — номер вершины

  • необязательно:
    1. label — пометка или обозначение вершины
    2. x — координата x на плоскости, где будет расположена вершина графа
    3. y — координата y на плоскости, где будет расположена вершина графа
    4. size — размер вершины


Для таблицы edges колонки следующие:
  • обязательные:
    1. source — id начальной вершины
    2. target — id конечной вершины

  • необязательные:
    1. label — пометка или обозначение ребра
    2. weight — вес ребра


Опциально доступны колонки «start» и «end» для динамических графов. После нескольких тестовых проверок было решено использовать SQLite3.

Скрипт заполнения БД на Python


Скрипт (программа) должна выполнять следующее:
  • Загружать данные об авторах статьи
  • Разделить данные об авторах на отдельные ФИО
  • Заполнять БД в соответствии с предыдущим пунктом

В виду того, что исходного кода достаточно много я не стал вставлять его в статью. Скачать его можно здесь.

Приведу лишь некоторые комментарии. В качестве БД использовалась sqlite3, интерфейс поддержка которой присутствует в python. Таблицы и колонки созданы в соответствии с описанием в разделе «Форматы файлов». «httр://eprint.iacr.org/cgi-bin/cite.pl?entry=year/number» использовалась в качестве исходной ссылки, где year — год публикации, number — номер статьи. Изначально предполагалось, что нужно перебирать с 001 до последнего, который определяется по отсутствию слова «author». Однако, потом выяснилось, что не все номера статей присутствуют (например, нет 001 в 2004 году). Поэтому пришлось нагородить велосипед на проверку 3-х подряд не найденных авторов. Ещё одних подвох ждал при получении ФИО. Строки авторов могут иметь вид:
"{Елена Прекрасная, Тугарин Змей и Алёша Попович}"
"{Елена Прекрасная, Тугарин Змей, и Алёша Попович}"
"{Елена Прекрасная, Тугарин Змей, и Ал{ee}ша Попович}"
"{Алёша Попович }"
"{Елена Прекрасная и Тугарин Змей}"

Кто подскажет как быстро из строк получить ФИО, буду благодарен. На выходе должно быть ['Елена Прекрасная','Тугарин Змей','Алёша Попович'] (без пробелов и запятых, т.е. просто имя и фамилия через пробел).

Ну и напоследок, чтобы не мучить интернет, я решил сначала создать локальный дамп авторов, а потом его использовать в качестве входных данных. Для этого я использовал pickle, который позволяет делать дамп переменных в файл, а после, в случае необходимости, извлекать. Для этого я создал словарь (dictionary). В качестве ключей выступали года, а значения — массив строк с авторами. Таким образом, я могу создавать БД по интересующим меня годам, используя лишь локальный файл.

Визуализация данных при помощи Gephi



В качестве примера возьмем маленький граф: года с 1996 по 2003. Он состоит из 759 вершин и 437 рёбер. Эту информацию можно увидеть при импортировании графа:



или в окне «Context».



Дополнительно, при импортировании можно выбрать ориентацию графа: ориентированный, неориентированный или смешанный.

Далее выберем окно «Ranking» для начального редактирования графа. В зависимости от степени, раскрасим все вершины в оттенки синего цвета и зададим размер самой вершины. Рекомендую задавать максимальный размер вершины, равный максимальной степени вершины или в 2 раза больше.

В конечном итоге получилось вот это:



Теперь, чтобы красиво всё представить, выберем окно «Layout». В этом окне представлены алгоритмы, которые можно использовать для упорядочивания графа.

Далее приводятся скриншоты некоторых из них.

ARF



Radial Axis



Parallel Force Atlas



Ещё вершины можно прикрепить к одной из осей, однако это выбирается в окне «Ranking» -> «Coordinates»



На графе можно выбрать вывод поля «label». Например:



Выводы



Gephi является хоть и молодым, но очень мощным средством визуализации различных данных, который подойдет как новичку, так и опытному пользователю. Использование баз данных позволяет быстро и легко получить необходимые входные данные для визуализации.
Oleksandr Kazymyrov @okazymyrov
карма
17,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (10)

  • +2
    Очень интересно!!! Вопрос как построить динамический граф, который можно проиграть потом или экспортировать в видео. То есть какие основные параметры должны быть у вершин и ребер, и как их писать в бд? Если знаете ответ конечно. Буду благодарен. Спс.
    • +1
      >> Опциально доступны колонки «start» и «end» для динамических графов.

      Для динамического графа можно использовать такую таблицу.

      create table nodes(
      id,
      label,
      x,
      y,
      size,
      start double,
      end double
      );

      Где start и end это начальное и конечное время (или значение double) отображение вершины на граве. Аналогично и для рёбер.

      Скриншоты делать можно. А вот поддержки видео пока что нет. Вот тут и тут ответ на этот вопрос.
      • 0
        спасибо. очень поможет.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +2
      Да, я согласен с вами.

      В плагине «Parallel Force Atlas» есть поддержка OpenMP и CUDA. К сожалению протестировать не могу, так как работает только Windows.

      Под Linux довольно быстро работает «ForceAtlas 2», так как там есть поддержка потоков. Если нормальный CPU, то сначала можно применить его (для сортировки), а потом уже другие.

      Ну и в некоторых плагинах есть параметр «speed», который в ущерб точность увеличивает производительность. Тоже можно использовать для сортировки.
  • 0
    Очень вовремя, как раз хотел с помощью Gephi нарисовать граф взаимодействий наших поисковых серверов. Спасибо!
    • 0
      Вот что получилось, если вдруг кому интересно:

  • 0
    На феервек похоже! :)
  • 0
    Я не нашёл — есть у него command line интерфейс?
    Спасибо!
    • 0
      Вроде как нет. Но, возможно, это вам поможет.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.