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

На правах рукописиКоломейченко Максим ИгоревичМатематическое и программное обеспечение визуального анализаграфовой информации сети взаимодействующих объектовСпециальность 05.13.11 – «Математическое и программное обеспечениевычислительных машин, комплексов и компьютерных сетей»АВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата технических наукМосква - 2017-Работа выполнена в Автономной некоммерческой организации «ИнститутФизико-Технической Информатики»Научный руководитель:Официальные оппоненты:Ведущая организация:доктор технических наук, доцентЧеповский Андрей Михайлович,профессор кафедры информационной безопасностиНационального исследовательского университетаВысшая школа экономикиМихайлюк Михаил Васильевич,доктор физико-математических наук, профессор,заведующий отделом программных средстввизуализации федерального государственногоучреждения Федерального научного центра«Научно-исследовательский институт системныхисследований Российской академии наук»(ФГУ ФНЦ НИИСИ РАН)Старков Сергей Олегович,докторфизико-математическихнаук,Обнинский институт атомной энергетики (ИАТЭ)Национальногоисследовательскогоядерногоуниверситета (НИЯУ) «МИФИ», заведующийкафедрой компьютерных систем, сетей итехнологийФедеральное государственное бюджетноеобразовательное учреждение высшего образования«Санкт-Петербургский национальныйисследовательский университет информационныхтехнологий, механики и оптики»Защита состоится 22 июня 2017 года в 15-00 часов на заседаниидиссертационного совета Д 212.131.05 при Московском технологическомуниверситете (МИРЭА) по адресу: Москва, Проспект Вернадского, д.

78, Д117С диссертацией можно ознакомиться в библиотеке Московскоготехнологического университета (МИРЭА) и на сайте организацииwww.mirea.ru.Автореферат разослан «хх» хххххх 2017 г.Ученый секретарь диссертационного совета Д 212.131.05,к.т.н., доцентАндрианова Елена Гельевна-3АктуальностьвзаимодействияОбщая характеристика работытемыисследования.Графовоесложныхвзаимодействующихпрограммныхобъектоввсистем,социальныхсетях,представлениеравноимееткакнеитолькотеоретический интерес, но и серьезное практическое применение в задачахобеспечениябезопасности.Такаязадачавозникаетприисследованиисоциальных сетей, анализе телекоммуникационного взаимодействия объектов,проведения расследованийметодамивизуальногоправоохранительнымианализа.органамиАктуальностьработыирешаетсяопределяетсяпотребностью в методах реализации интерфейсов программных комплексов дляанализа графов, возникающей в задачах антитеррористической деятельности,социологического и экономического анализа.Несмотря на многообразие библиотек для создания инструментоввизуализации сетей, в существующих программных продуктах наблюдается ряднедостатков: отсутствие платформенно-независимых решений, отсутствиесобственных специализированных хранилищ, человеко-машинные интерфейсысистем не ориентированы на аналитическую работу с графами большихразмеров по причине отсутствия встроенных в системы визуализации многихэффективных методов автоматического размещения объектов (многополосноеразмещение, разделение по группам взаимосвязанных объектов).Прианализевзаимодействующихобъектоввозникаютпроблемывизуального анализа структуры графов больших размеров.

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

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

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

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

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