Так уж случилось, что я оказался ассистентом у профессора в университете. Никогда не думал, что прийдётся сталкиваться с оценкой рисков и визуализацией данных, будучи, по призванию, криптографом. Курс называется «Информационные сети» и включает в себя: анализ случайных процессов, моделирование малых миров; компьютерные алгоритмы для оценки свойств сети; экспериментальные исследования крупных сетей, а также анализ рисков, которые трудно предсказать.
В виду того, что курс читается в основном для ИТ-шников, лектор сделал ставку на то, чтобы дать достаточно теории с минимумом математики и большим количеством практики. Для большинства вышеупомянутых задач подходит программа NetLogo. Она включает собственный язык программирования высокого уровня, который позволяет с лёгкостью моделировать различные случайные процессы. Для визуализации разнообразных данных была выбрана программа Gephi.
На основе опыта использования последней и была написана статья, в которой рассматривается получение входных данных для ПО с последующей их визуализацией.
Собственно постановка задачи была таковой: визуализация каких-либо реальных данных средствами Gephi.
После некоторых размышлений решил представить взаимодействия авторов с сайта IACR. Кто работает в области защиты информации наверняка знают про него, для всех остальных — это сайт, где в открытом доступе представлены статьи по информационной безопасности.
Gephi понимает достаточно большое количество форматов файлов.
Как видно из рисунка, самый лучший вариант — использовать 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 должна содержать колонки:
Для таблицы edges колонки следующие:
Опциально доступны колонки «start» и «end» для динамических графов. После нескольких тестовых проверок было решено использовать SQLite3.
Скрипт (программа) должна выполнять следующее:
В виду того, что исходного кода достаточно много я не стал вставлять его в статью. Скачать его можно здесь.
Приведу лишь некоторые комментарии. В качестве БД использовалась sqlite3, интерфейс поддержка которой присутствует в python. Таблицы и колонки созданы в соответствии с описанием в разделе «Форматы файлов». «httр://eprint.iacr.org/cgi-bin/cite.pl?entry=year/number» использовалась в качестве исходной ссылки, где year — год публикации, number — номер статьи. Изначально предполагалось, что нужно перебирать с 001 до последнего, который определяется по отсутствию слова «author». Однако, потом выяснилось, что не все номера статей присутствуют (например, нет 001 в 2004 году). Поэтому пришлось нагородить велосипед на проверку 3-х подряд не найденных авторов. Ещё одних подвох ждал при получении ФИО. Строки авторов могут иметь вид:
"{Елена Прекрасная, Тугарин Змей и Алёша Попович}"
"{Елена Прекрасная, Тугарин Змей, и Алёша Попович}"
"{Елена Прекрасная, Тугарин Змей, и Ал{ee}ша Попович}"
"{Алёша Попович }"
"{Елена Прекрасная и Тугарин Змей}"
Кто подскажет как быстро из строк получить ФИО, буду благодарен. На выходе должно быть ['Елена Прекрасная','Тугарин Змей','Алёша Попович'] (без пробелов и запятых, т.е. просто имя и фамилия через пробел).
Ну и напоследок, чтобы не мучить интернет, я решил сначала создать локальный дамп авторов, а потом его использовать в качестве входных данных. Для этого я использовал pickle, который позволяет делать дамп переменных в файл, а после, в случае необходимости, извлекать. Для этого я создал словарь (dictionary). В качестве ключей выступали года, а значения — массив строк с авторами. Таким образом, я могу создавать БД по интересующим меня годам, используя лишь локальный файл.
В качестве примера возьмем маленький граф: года с 1996 по 2003. Он состоит из 759 вершин и 437 рёбер. Эту информацию можно увидеть при импортировании графа:
или в окне «Context».
Дополнительно, при импортировании можно выбрать ориентацию графа: ориентированный, неориентированный или смешанный.
Далее выберем окно «Ranking» для начального редактирования графа. В зависимости от степени, раскрасим все вершины в оттенки синего цвета и зададим размер самой вершины. Рекомендую задавать максимальный размер вершины, равный максимальной степени вершины или в 2 раза больше.
В конечном итоге получилось вот это:
Теперь, чтобы красиво всё представить, выберем окно «Layout». В этом окне представлены алгоритмы, которые можно использовать для упорядочивания графа.
Далее приводятся скриншоты некоторых из них.
ARF
Radial Axis
Parallel Force Atlas
Ещё вершины можно прикрепить к одной из осей, однако это выбирается в окне «Ranking» -> «Coordinates»
На графе можно выбрать вывод поля «label». Например:
Gephi является хоть и молодым, но очень мощным средством визуализации различных данных, который подойдет как новичку, так и опытному пользователю. Использование баз данных позволяет быстро и легко получить необходимые входные данные для визуализации.
В виду того, что курс читается в основном для ИТ-шников, лектор сделал ставку на то, чтобы дать достаточно теории с минимумом математики и большим количеством практики. Для большинства вышеупомянутых задач подходит программа NetLogo. Она включает собственный язык программирования высокого уровня, который позволяет с лёгкостью моделировать различные случайные процессы. Для визуализации разнообразных данных была выбрана программа Gephi.
На основе опыта использования последней и была написана статья, в которой рассматривается получение входных данных для ПО с последующей их визуализацией.
Собственно постановка задачи была таковой: визуализация каких-либо реальных данных средствами Gephi.
Генерация данных
После некоторых размышлений решил представить взаимодействия авторов с сайта IACR. Кто работает в области защиты информации наверняка знают про него, для всех остальных — это сайт, где в открытом доступе представлены статьи по информационной безопасности.
Форматы файлов Gephi
Gephi понимает достаточно большое количество форматов файлов.
Как видно из рисунка, самый лучший вариант — использовать 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 должна содержать колонки:
- обязательно:
- id — номер вершины
- необязательно:
- label — пометка или обозначение вершины
- x — координата x на плоскости, где будет расположена вершина графа
- y — координата y на плоскости, где будет расположена вершина графа
- size — размер вершины
Для таблицы edges колонки следующие:
- обязательные:
- source — id начальной вершины
- target — id конечной вершины
- необязательные:
- label — пометка или обозначение ребра
- 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 является хоть и молодым, но очень мощным средством визуализации различных данных, который подойдет как новичку, так и опытному пользователю. Использование баз данных позволяет быстро и легко получить необходимые входные данные для визуализации.
