Диссертация (Математическое и программное обеспечение визуального анализа графовой информации сети взаимодействующих объектов), страница 2

Основные результаты исследований изложены в 10научных трудах [74 - 83], 4 из которых [74 - 77] опубликованы в изданиях,рекомендованных ВАК, или приравненных к ним изданиям.Личный вклад автора. Основные научные результаты получены авторомлично. К основным научным результатам, полученным автором лично относятсянижеперечисленные положения, опубликованные в работах из списка литературы:• методики построения размещения объектов для визуализации связей графана основе метода физических аналогий и их реализация в [74, 75, 82, 83];• алгоритмы построения многополосного размещения для визуализации связейвыделенного множества объектов графа и их реализация в [75, 80];9• алгоритмы выявления сообществ графа взаимодействующих объектов сцелью визуализации структуры графа на плоскости в [76, 77];• эффективные структуры данных для хранения индексов и графов большихразмеров в [74, 78, 81];• архитектура комплекса визуализации и анализа графов больших размеров иее реализация в [74, 75, 79, 82, 83];Другим соавторам принадлежат математические обоснования алгоритмов,внедрение разработанных моделей и алгоритмов.Структура и объем работы.

Диссертация состоит из введения, четырех глав,выводов, библиографического списка, включающего в себя 84 наименования, иодного приложения. Работа содержит 156 страниц машинописного текста основнойчасти, включающих 60 рисунков, 1 таблицу и 10 страниц библиографии,включающей в себя 84 наименования, Приложение А содержит 73 страницы текста,включающих 76 рисунков.

Приложение Б содержит три акта о внедрении.В первой главе «Средства визуального анализа графов» приведен обзорнаиболее распространенных программных продуктов, предназначенных длявизуализации графов с целью анализа структуры графа. Описаны существующиеметодики многополосного размещения объектов на плоскости. Приведен обзоралгоритмов выделения сообществ в графе взаимодействующих объектов.Во второй главе «Геометрические модели автоматических размещенийобъектовграфаавтоматическогонаплоскости»размещенияописаныграфанагеометрическиеплоскости,моделипозволяющиедляделатьэффективный визуальный анализ структуры графа. Описана геометрическаямодель автоматического размещений объектов графа на плоскости, базирующегосянаметодефизическиханалогий.Разработаныгеометрическиепозволяющие реализовывать многополосное размещение объектов графа.модели,10В третей главе «Визуальный анализ графа социальной сети, допускающеговыделение подграфов» предложен алгоритм выделения сообществ в сетяхвзаимодействующих объектов.

Описана предложенная геометрическая модельвизуализации на основе графа с выделенными сообществами.В четвертой главе «Программный комплекс визуального анализа графов»описаны архитектура и принципы реализации программного комплекса длявизуального анализа графов больших размеров.В «Основных результатах работы» сформулированы основные выводы ирезультаты диссертационной работы.В Приложении А описана основная функциональность интерфейсаразработанного программного комплекса.Приложение Б содержит акты о внедренииГЛАВА 1. Средства визуального анализа графаПрограммное обеспечение для анализа графов1.1.1.1.1.Существующие средства анализаПри анализе графов взаимодествующих объектов, социальных сетейвозникает задача визуального представления их структур [3, 18, 38]. Необходимоедля этого программное обеспечения должно предоставлять широкие возможностидля визуализации и анализа сетей c большим количеством вершин. Областьприменения такого программного обеспечения обширна [3, 18, 52] и затрагиваетмногие смежные дисциплины, такие как социология, психология, политология,маркетинг.Существует много промышленных продуктов для анализа графов.

Например,i2 Analyst’s Notebook [37], Sentinel Visualizer [65], CrimeLink [24], Xanalys LinkExplorer [71], Gephi [32], Tom Sawyer Software [67], igraph [36], NetMiner4 [49],Cytoscape [25], VisuaLyzer [70], Tulip [68], COSBILab [23], Графоанализатор [4],GraphViz [34], yED [73], aiSee [16], Visual Graph [9, 69].Gephi [32] – инструмент для аналитиков данных и исследователей,позволяющий проводить анализ и визуализацию графов (Рис. 1.1). У пользователяесть возможность управлять визуальным представлением графа и интерактивновзаимодействовать с ним. Основные характеристики Gephi:• исходный код: доступен (open-source);• операционная система: Windows, Mac OS X and Linux;• форматы импорта: txt, csv, xls, graphml;• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: до 100 000 вершин и 1 000 000 связей;12• алгоритмы авторазмещений: круговое размещение, гео-размещение, 4алгоритма на основе метода физических аналогий, радиальное размещение;• дополнительные инструменты анализа: выделение сообществ, подсчетметрик центральности вершин и связей.Рис.

1.1. Gephi – пример пользовательского интерфейса.NetMiner [49] – коммерческий программный продукт для анализа ивизуализации больших социальных сетей, основные характеристики которого:• исходный код: недоступен;• операционная система: Windows XP/ Vista/ 7 / 8;• форматы импорта: xls (excel) , xlsx (excel 2007), csv (text), dl (ucinet), net(pajek), dat(stocnet), gml, nmf;• интерактивноевзаимодействиесграфом(Рис.1.2):инструментывизуализации и навигации, инструменты редактирования графа и еговизуального представления;13• ограничения на визуализацию: по утверждению разработчиков более10 000 000 вершин, по числу ребер информация отсутствует, в бесплатнойверсии продукта - 100 вершин;• алгоритмыавторазмещений:3dразмещение,круговоеразмещение,размещение на основе кластеризации графа, размещение на основе методафизических аналогий;• дополнительные инструменты анализа: содержат большое число метрик дляанализа социальных сетей: гомофилия (homophily), множественность(multiplexity), взаимность (mutuality), сетевая закрытость (network closure);метрик, которые отражают характеристики графа поделённого на сегменты:клика (cliques), социальный круг (social circles), коэффициент кластеризации(сlustering coefficient), сплоченность (сohesion); для анализа графов:нахождение мостов, диаметра, плотности графа, расстояния между двумявершинами, коэффициент центральности;• дополнительно: предусмотрен как графический интерфейс, встроенныйскриптовый язык, основанный на рython.Cytoscape [25] – программный продукт (Рис.

1.3) с открытым исходнымкодом для визуализации и анализа сетей взаимодействующих молекул ибиологическихпутей.Изначальнобылразработандлябиологическихисследований, теперь используется для анализа и визуализации сложных сетей.Основные характеристики:• исходный код: доступен (open-source);• операционная система: написан на Java и может быть запущен из под любойоперационной системы, поддерживающей ее;• форматы импорта: sif (simple interaction format), gml, fgmml, biopax, psi-mi,graphml, kgml (kegg xml), sbml, obo, gene association. csv, ms excel;14Рис. 1.2.

NetMiner 4 – пример пользовательского интерфейса.• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: размер графов при визуализации ограниченнесколькими сотнями тысяч объектов, тест на работу с большим графом (300000 вершин и 2 млн. связей) показал, что обработка таких объемов уже неможет проходить в реальном времени;• алгоритмы авторазмещений: круговое, иерархическое, на основе методафизических аналогий;15• дополнительные инструменты анализа: имеется возможность примененияфильтров для выделения подграфов по определенным параметрам, возможенпоиск кластеров, нахождение наиболее значимых подсетей;• дополнительно: доступна возможность подключения собственных плагинов.Рис.

1.3. Cytoscape – пример пользовательского интерфейса.VisuaLyzer [65] (Рис. 1.4) – интерактивный инструмент для анализа ивизуализации графов социальных сетей с следующими характеристиками:• исходный код: недоступен;• операционная система: Windows 2000/XP/7/8;• форматыGraphML;импорта: edgelist/edgearray/nodelist,Excel,CSV,DyNetML,16• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: предназначен для работы с графамималеньких и средних размеров (из документации);• алгоритмы авторазмещений: на основе метода физических аналогий, наоснове кругового размещения;• дополнительные инструменты анализа: нахождения диаметра, плотностиграфа,кратчайшегопутимежду двумявершинами,коэффициентацентральности, нахождение ближайших соседей, подграфов и сообществ.Рис.

1.4. VisuaLyzer – пример пользовательского интерфейса.Tulip [68] – аналитическая платформа (набор инструментов в видебиблиотеки), направленная на исследование и визуализацию реляционных данных.Основные характеристики:•исходный код: доступен (open-source);• операционная система: Linux, Windows, Mac OS;17• форматы импорта: tulip format (.tlp), graphviz (.dot), gml, txt, adjacency matrix,csv, gexf, pajek;• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: позволяет визуализировать и редактироватьграфы размерами до 10 000 000 вершин и связей, однако, для графа из 300000 вершин и 2 млн.

ребер визуализация и алгоритм кругового размещенияработают нестабильно и медленно (далеко не в режиме реального времени);• алгоритмы авторазмещений: круговое, иерархическое, на основе методафизических аналогий;• дополнительные инструменты анализа: подсчет метрик центральности иалгоритм иерархической кластеризации;• дополнительно:реализованаинтеграцияспопулярнойзарубежнойсоциальной сетью FaceBook и возможен импорт друзей, есть возможностьдобавлять новые плагины, в том числе через интерфейс пользователя наязыке python.CoSBiLab [23] – инструмент для визуализации и анализа ориентированных инеориентированных графов, с следующими основными характеристиками:• исходный код: недоступен;• операционная система: Windows;• форматы импорта: dot, txt, dl, spec;• интерактивное взаимодействие с графом: инструменты визуализации инавигации,инструментыредактированияграфаиеговизуальногопредставления;• ограничения на визуализацию: информация отсутствует;• алгоритмы авторазмещений: случайное, круговое, на основе методафизических аналогий;18• дополнительныеинструментыанализа:подсчетразличныхметрикцетральности вершин и связей, поиск циклов и кратчайших путей,кластеризация графа.Графоанализатор [4] - приложение с открытым исходным кодом,используемое в учебных целях, которое обладает следующими основнымихарактеристиками:• исходный код: доступен;• операционная система: Windows;• форматы импорта: ввод графа через задание матрицы или списка смежности;• интерактивное взаимодействие с графом: позволяет визуализировать графы;• ограничения на визуализацию: информация отсутствует;• алгоритмы авторазмещений: отсутствуют;• дополнительные инструменты анализа: поиск минимального пути, поискэйлеровых и гамильтоновых маршрутов, поиск минимального оставногодерева, определение максимального потока как для одного стока и истока,так и для множества стоков и истоков, проверка на связность, поиск радиусаи диаметра графа, проверка, является ли граф деревом, проверка напланарность, возможность сохранения и загрузки графа с поддержкойсохранения визуального представления.GraphViz [34] - пакет утилит по автоматической визуализации графов,заданных в виде описания на языке dot, а также дополнительных tui и gui программ,виджетов и библиотек, используемых при разработке программного обеспечениядля визуализации структурированных данных.