Диссертация (1090614), страница 3
Текст из файла (страница 3)
Пакет Graphviz разработанспециалистами лаборатории AT&T и распространяется с открытыми исходнымифайлами по лицензии EPL (Eclipse Public License). Основные характеристики:• исходный код: доступен;• операционная система: Linux, Mac OS, MS Windows;• форматы импорта: csv, txt;19• интерактивное взаимодействие с графом: инструмент dotty – графическийпользовательский интерфейс для создания графов;• ограничения на визуализацию: предназначен для работы с небольшимиграфами, явных ограничений на размер не наклыдвается;• алгоритмы авторазмещений: twopi, circo - инструменты кругового имножественного кругового автоматического размещения, neato, fdp, sfdp инструменты автоматического размещения графа на основе методафизических аналогий;• дополнительныемногоуровневогоинструментыграфасанализа:dot-возможностьюинструментвыводасозданияизображениярезультирующего графа во множестве форматов (png, pdf, postscript, svg ит.д.).yEd [73] – бесплатная программа, построенная на базе java-библиотеки длявизуализации графов с следующими основными характеристиками:• исходный код: недоступен;• операционная система: Windows, Mac OS X, Linux;• форматы импорта: xls, xml, gml, gedcom;• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: информация отсутствует;• алгоритмы авторазмещений: иерархический, круговой, на основе методафизических аналогий, многоуровневый круговой;• дополнительные инструменты анализа: подсчет метрик центральности,поиск кратчайших путей, реализован экспорт в форматы png, jpg, svg, pdf,swf.aiSee [16] –приложение, больше не поддерживаемое как отдельный продуктдля анализа и визуализации графов.
Размер обрабатываемых графов ограничен20несколькими сотнями тысяч вершин. Используется для автоматическогоразмещения графов на плоскости. Детальная информация отсутствует.i2 Analyst’s Notebook [37] – визуальная аналитическая среда, позволяющаяанализировать, сопоставлять и визуализировать данные из различных источников,там самым уменьшая время на выделение важной информации из данных.Направление анализа связано с выявлением преступной, террористической имошеннической деятельностей.
Основные характеристики:• исходный код: недоступен;• операционная система: Windows;• форматы импорта: csv, txt, xml, xls, doc;• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: официальная информация отсутствует,экспериментальным путем установлено, что для схем с количеством вершини связейболее 10 000, отклик программного продукта при навигациисущественно замедляется;• алгоритмыавторазмещений:круговоеавторазмещение,групповое,иерархическое, временное (упорядоченное и пропорциональное), на основеметода физических аналогий, и размещение, минимизирующее количествопересекающихся связей;• дополнительные инструменты анализа: присутствуют.С точки зрения инструментов визуализации данных, этот продуктпредоставляет довольно богатую функциональность: ручное добавление вершин исвязей, настройка отображения объектов (цвета, шрифты, иконки, стили), имеетудобные инструменты перемещения и масштабирования по схеме, присутствуетвозможность добавления атрибутов к объектам на схеме.
Имеется возможностьотображения множественных связей между вершинами графа.21В i2 Analyst’s Notebook реализован импорт из различных форматов (csv, txt,xml, xls, doc) данных в виде пошагового мастера, с возможностью визуальногопред-просмотра финального результата. В качестве инструментов визуальногоанализа данное программное обеспечение выделяется большим количествомвстроенных алгоритмов автоматического размещение вершин и связей на схеме:круговое авторазмещение, групповое, иерархическое, временное (упорядоченное ипропорциональное), на основе метода физических аналогий, и размещение,минимизирующее количество пересекающихся связей.Функциональность программы не ограничивается лишь графическимпредствлением данных, предоставляя широкой набор инструментов анализа: поискразличных кратчайших путей между вершинами, в том числе и с учетом атрибутоввремени, кластеризация для поиска наиболее тесно связанных объектов, поискобъектов, похожих друг на друга по набору заданных условий, поиск объектов нетолько по значениям атрибутов, но и с помощью генерации графических запросов,построение базовых метрик центральности для вершин и связей.
Официальныеисточники не раскрывают точные цифры по ограничениям на количество объектовдля одновременной визуализации в режими реального времени.Visual Graph [9, 69] – отечественная программа, распространяемая полицензииBSD, в первую очередь для визуализации атрибутированныхиерархическихграфов.Создаётсяврамкахведущегосявлабораторииконструирования и оптимизации программ ИСИ СО РАН проекта по разработкеметодов и средств для визуализации сложно структурированной информациибольшого объема на основе графовых моделей. Программное обеспечение (Рис.1.5) адаптировано под использование разработчиками систем конструированияпрограмм (компиляторы) для визуализации структур данных, возникающих приработе этих систем.
Основные характеристики:• исходный код: доступен, лицензия BSD;• форматы импорта: graphml;22• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: до 100 000 вершин и связей;• алгоритмы авторазмещений: круговое, иерархические;• дополнительные инструменты анализа: подсветка кратчайшего пути, циклов,а также поиск максимального общего подграфа двух графов;• дополнительно: в качестве базы данных для хранения графов используетсяSQLite, присутствует возможность добавления новой функциональности ввиде плагинов.Рис.
1.6. Visual Graph – пример пользовательского интерфейса.i2 Analyst’s Notebook, CrimeLink, Sentinel Visualizer и Xanalys Link Explorerявляются программными продуктами, предназначенными для анализа системвзаимосвязанных объектов, а также изучения динамики последовательныхсобытий. Tom Sawyer Software и igraph представляет собой набор библиотек длясоздания инструментов визуализации и анализа сетей из различных предметных23областей. Несмотря на некоторые различия в деталях, по предоставляемойфункциональности и назначению эти системы визуализации во многом схожи.Программные средства анализа графов обязательно содержат модулиавтоматического размещения, предназначенные для автоматического размещениеобъектов [37, 67] и реализуют графические схемы размещения объектов, типа"павлиний хвост", круговое размещение, покомпонентное круговое размещение.У большинства современных промышленных систем присутствует ряднедостатков:отсутствиеплатформенно-независимыхрешений,отсутствиесобственных специализированных хранилищ, системы не ориентированы наработу с большими графами, некоторые системы устарели или пересталиподдерживаться.Отдельно стоит отметить, исходя из проведенного анализа, что у некоторыхсистем, таких как VisuaLyzer [65], CoSBiLab [23], Графоанализатор [4], GraphViz [34],yEd [73], aiSee [16], отсутствует информация об ограничении на размерывизуализируемых графов.
У таких продуктов, как Visual Graph [9, 69], i2 Analyst’sNotebook [37], Cytoscape [25], Gephi [32] , нет поддержки визуализации большихграфов, они лимитированы объемами вплоть до 100 000 вершин. У несколькихпродуктов (Tulip [68], NetMiner [49]) не удалось подтвердить заявленные цифры повизуализации в размере 10 000 000 вершин. Также понятно, что объемыобрабатываемых графов на практике не ограничиваются этими цифрами, чтоделает непригодным использование этих систем при решении прикладныхпромышленных задач.Далее приводится обобщённое описание функциональности основныхвышеперечисленных программных средств, которое включает в себя:• способы визуального представления информации;• способы автоматического размещения элементов изображения;• инструменты выделения интересующей информации из общего объёма;• инструменты анализа и способы визуального представления результатов.24Далее будут использоваться сокращенные названия при указании продукта:• i2 ANB — i2 Analyst’s Notebook;• SV — Sentinel Visualizer;• CL — CrimeLink;• XLE — Xanalys Link Explorer;• TSS — Tom Sawyer Software.1.1.2.Способы визуального представления информацииВ процессе работы необходимая информация отображается в видедвумерных графических схем.
Для представления информации о структуре связейиспользуют схемы трёх базовых типов [17, 18, 38]:• Сетевые схемы используются для отображения структуры связей междуобъектами. Объекты размещаются на схеме из соображений наглядностиизображения.• Временные схемы используются для отображения взаимосвязи междусобытиями и объектами предметной области. Вводится горизонтальнаявременная ось, положение узлов-событий и связей-событий по горизонталиопределяется значениями временных атрибутов. Масштаб временной осиможет не быть равномерным на всём протяжении. Для временного анализапоследовательности событий без привязки к структуре связей используютсякруговые и линейные временные диаграммы.• Геопространственные схемы используются для отображения связей междуобъектами, имеющими географическую привязку. Положение объектов насхемеопределяетсягеографическимикоординатами.Необходимыйфрагмент карты может быть импортирован из Google Earth.В качестве дополнительного представления структуры связей в некоторыхпродуктах в явном виде используется матрица смежности.25На практике часто используются комбинированные схемы, в которыхотдельныечастивизуализируютсявсоответствиисизобразительнымисоглашениями различных базовых типов.Примеры сетевых схем приведены на рисунках 1.6 – 1.8.Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
