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

Автономная некоммерческая организация«Институт Физико-Технической Информатики»На правах рукописиКоломейченко Максим ИгоревичМатематическое и программное обеспечениевизуального анализа графовой информациисети взаимодействующих объектовСпециальность 05.13.11 – «Математическое и программное обеспечениевычислительных машин, комплексов и компьютерных сетей»ДИССЕРТАЦИЯна соискание учёной степеникандидата технических наукНаучный руководитель:доктор технических наук, доцентЧеповский Андрей МихайловичМосква — 20162СОДЕРЖАНИЕВВЕДЕНИЕ ................................................................................................................. 4ГЛАВА 1.Средства визуального анализа графа ............................................ 111.1.Программное обеспечение для анализа графов ........................................

111.2.Многополосное размещение ...................................................................... 351.3.Визуальный анализ структуры графа взаимодействующих объектов наоснове выделения «сообществ» ............................................................................. 391.4.Выводы по 1 главе ...................................................................................... 51ГЛАВА 2.Геометрические модели автоматических размещений объектовграфа на плоскости .................................................................................................. 522.1.Базовые геометрические модели автоматического размещений ............. 522.2.Геометрическая модель автоматического размещений на основе методафизических аналогий ............................................................................................. 602.3.Многополосное размещение ......................................................................

692.4.Выводы по 2 главе ...................................................................................... 89ГЛАВА 3.Визуальный анализ графа социальной сети, допускающеговыделение подграфов .............................................................................................. 903.1.Методика выделения сообществ................................................................ 903.2.Вычислительные эксперименты ................................................................

983.3.Построение геометрической модели автоматического размещенияобъектов графа с выделенными сообществами .................................................. 1013.4.Выводы по 3 главе .................................................................................... 120ГЛАВА 4.4.1.Программный комплекс визуального анализа графов ............ 121Общая архитектура программного комплекса ........................................

12134.2.Хранение данных ...................................................................................... 1284.3.Используемые структуры данных ........................................................... 1324.4.Инструменты анализа ............................................................................... 1394.5.Выводы по 4 главе .................................................................................... 144ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ ............................................................. 145СПИСОК ЛИТЕРАТУРЫ ....................................................................................

147ПРИЛОЖЕНИЕ А. Описание функциональности программного комплекса................................................................................................................................... 157ПРИЛОЖЕНИЕ Б. Акты внедрения .................................................................. 2304ВВЕДЕНИЕАктуальностьтемыисследования.Графовоепредставлениевзаимодействия сложных программных систем, равно как и взаимодействующихобъектов в социальных сетях, имеет не только теоретический интерес, но исерьезное практическое применение в задачах обеспечения безопасности. Такаязадачавозникаетприисследованиисоциальныхсетей,анализетелекоммуникационного взаимодействия объектов, проведения расследованийправоохранительными органами и решается методами визуального анализа.Актуальность работы определяетсяпотребностью в методах реализацииинтерфейсов программных комплексов для анализа графов, возникающей в задачахантитеррористической деятельности, социологического и экономического анализа.Несмотрянамногообразиебиблиотекдлясозданияинструментоввизуализации сетей, в существующих программных продуктах наблюдается ряднедостатков:отсутствиеплатформенно-независимыхрешений,отсутствиесобственных специализированных хранилищ, человеко-машинные интерфейсысистем не ориентированы на аналитическую работу с графами больших размеровпо причине отсутствия встроенных в системы визуализации многих эффективныхметодов автоматического размещения объектов (многополосное размещение,разделение по группам взаимосвязанных объектов).Прианализевзаимодействующихобъектоввозникаютпроблемывизуального анализа структуры графов больших размеров.

Поэтому длявизуализации множества взаимодействующих объектов требуется разработка иреализация методов многополосного размещения и разделение по группамвзаимосвязанных объектов, эффективных модификаций метода физическиханалогий.5Решаемая научная и практическая задача состоит в разработке и реализацииэффективных с точки зрения скорости и обрабатываемых объемов алгоритмов иархитектурных решений программного обеспечения, позволяющего средствамичеловеко-машинных интерфейсов проводить аналитический анализ графов.Объект исследования – параметры расположения объектов графа наплоскости при его визуальном представлении в программном интерфейсе.Предмет исследования – методы и алгоритмы автоматического размещенияобъектов графа при его визуализации в человеко-машинном интерфейсе программанализа структуры графа.Целью диссертационной работы является решение задач автоматическогоразмещения элементов графа на плоскости для задач визуального анализаструктуры взаимодействия объектов.Для достижения поставленной цели требуется решение следующих задач:1.

Разработать универсальные геометрические модели для реализации методовавтоматического размещения объектов графа больших размеров с цельюанализа структуры графа.2. Разработать алгоритмы для создания процедур нахождения и визуализациисвязанных групп вершин (сообществ) в анализируемых графах.3. Разработать архитектуру и принципы реализации человеко-машинногоинтерфейса программного комплекса, включающие методы визуализации ихранения графов больших размеров с целью анализа их структуры.Методы исследования. Диссертационная работа базируется на методах:теории графов, теории множеств, методах компьютерной графики и численныхметодах.Научная новизна результатов исследования состоит в том, что1. Разработан алгоритм автоматического размещения «быстрый павлиний хвост»,основанный на методе физических аналогий и оптимизирующий скоростные6характеристики алгоритма метода физических аналогий за счет анализа тольколокальной области на плоскости.2.

Предложены и реализованы в человеко-машинном интерфейсе геометрическиемодели, основанные на разработанных многополосных размещениях графа наплоскости, включающие формализацию процедуры расположения смежных слинией темы вершин и учитывающие визуальные характеристики (размеры)при размещении вторичных вершин относительно линии темы.3. Разработан и реализован метод выделения групп взаимодействующихобъектов, применимый к большим данным реальных сетей.4. Разработана и реализована в программном интерфейсе геометрическая модельавтоматическогоразмещениянаплоскостигруппсвязанныхвершин(сообществ) графа.Практическаязначимость.Научныеипрактическиерезультатыдиссертации использованы при разработке информационных систем и проведениянаучно-исследовательскихиопытно-конструкторскихработ,очемсвидетельствуют: акт о внедрении результатов диссертационного исследования,предоставленный ЗАО «Медианн-Решения»: акт об использовании результатовдиссертации,предоставленныйМеждународнымЦентромпоЯдернойбезопасности (АНО МЦЯБ); акт о внедрении результатов диссертационногоисследования,предоставленныйАОРДТЕХ.Результатыдиссертациииспользованы в учебном пособии [84].Результаты исследований по теме диссертационной работы использованыпри выполнении научно-исследовательских работ по следующим грантам РФФИ:• Проект № 16-07-00641 «Исследование и разработка математических моделей,методов и алгоритмов визуализации и анализа графов на примере социальныхсетей»7• Проект № 16-29-09546 «Разработка новых методов мониторинга и комплексноголингвистического и тематического анализа сообщений социальных медиа вцелях противодействия экстремизму и терроризму».Основные положения, выносимые на защиту:1.

Методика оптимизации скоростных характеристик алгоритма построенияразмещения объектов для визуализации связей графа на основе методафизических аналогий.2. Алгоритмы построения многополосного размещения для визуализации связейвыделенного множества объектов графа.3. Геометрическая модель и алгоритм для выделения в графе групп связанныхвершин (сообществ) и автоматического их размещения на плоскости с цельювизуального анализа в рамках программного интерфейса.4.

Архитектура программного комплекса визуализации и хранения графовбольших размеров с целью анализа их структуры средствами человекомашинного интерфейса и используемые в программном комплексе структурыданных.Достоверность результатов и обоснованность научных положенийдиссертационной работы обеспечивается корректным использованием методовтеории графов, теории алгоритмов и математического аппарата прикладнойматематики.Достоверностьполученныхвыводовподтверждаетсятакжесогласованностью с имеющимися результатами других авторов, результатамиэкспериментальных исследований и апробации работы. Достоверность результатовработы подтверждается работоспособностью предложенных методов и алгоритмовпри опытной и промышленной эксплуатации разработанного программногообеспечения.Апробацияработы.Материалыдиссертациидокладывалисьнамеждународных конференциях: Международной конференции по физико-8технической информатике CPT-2013, 12-19 мая 2013 г., Ларнака, Республика Кипр;Международной научной конференции Международного центра по ядернойбезопасностиИнститутафизико-техническойинформатикиSCVRT2013,Протвино, 25-29 ноября 2013 г.; Ершовской конференции по информатике 2014,Санкт-Петербург, 2014 г.; Международной научной конференции по физикотехнической информатике (CPT2015), 10-17 мая 2015 г., Ларнака, РеспубликаКипр; III Международной научно-практической конференции «Управлениеинформационной безопасностью в современном обществе», Москва, 19-21 мая2015 г.; IV Международной научно-практической конференции «Управлениеинформационной безопасностью в современном обществе», Москва, 31 мая-2 июня2016г.;Международнойнаучнойконференциипофизико-техническойинформатике (CPT2016), 8-15 мая 2016 г., Ларнака, Республика Кипр; 26Международной конференции GraphiCon2016, Нижний Новгород, 19-23 сентября2016 г.; Международной научной конференции Московского физико-техническогоинститута (государственного университета) и Института физико-техническойинформатики (SCVRT16), Протвино, 21-24 ноября 2016 г.Публикации.