Автореферат (Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов)

23ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность темы исследования. Графовые модели систем (ГМС) – математические модели структур систем, широко применяемые как в теоретических,так и в прикладных исследованиях. С 2003 года в рамках научного направленияDATA MINING активно развивается самостоятельное направление GRAPH MINING с ежегодным обсуждением результатов на международных симпозиумах. Вкачестве актуальных направлений отмечены исследование вопросов поиска исравнительного анализа структурной информации, а также получения знаний наоснове анализа данных, представленных ГМС. В настоящее время акцент переместился на поиск наиболее близких по сходству структур.

Сходство структур систем, являясь ключевым понятием системологии, требует исследований, направленных на создание новых поколений информационно-поисковых систем структурной информации (ИПССИ) (семантический web-поиск), экспертных систем,интеллектуальных систем поддержки принятия решений (ИСППР), на разработкуновых подходов в реализации правдоподобных рассуждений, на развитие анализаотношений структурной эквивалентности и толерантности систем (структурнаяинформатика, хим- и био-информатика), на разработку новых подходов в структурном распознавании образов.Работа продолжает исследования в рамках научной дисциплины – «структурная информатика», теоретической основой которой является «структурный спектральный анализ систем» (СС-анализ), и позволяет на общей теоретико-графовойоснове строить эффективные алгоритмы решения базовых задач структурной информатики.

Наиболее сложными и значимыми в теоретическом и прикладном аспектах являются задачи определения сходства и кластеризации ГМС1.В настоящее время задачи анализа сходства остались не исследованными дляорграфов, которые являются наиболее общим классом графов, имеющим широкий спектр теоретических и практических применений. Обобщая результаты исследований, которые получили Скоробогатов В.А., Добрынин А.А., Кохов В.А.,Грызунов А.Б., Ткаченко С.В., Незнанов А.А., Ибрахим А.Р., Джасим М.Р., Климентовский А.Н., Bunke H., Shearer K., Mekenyan O., Bonchev D. и др., актуальнойзадачей является разработка общей концепции, объединяющей подструктурную инадструктурную характеризации орграфов и их структурных инвариантов, характеризующих расположение фрагментов, что необходимо для формирования иисследования новых видов отношений структурной эквивалентности и толерантности систем, расширения возможностей и повышения эффективности компьютерных методов анализа сходства ГМС.

Проблема анализа сходства орграфов сучетом расположения и сходства расположения фрагментов актуализированаещё более ввиду того, что Журавлёв Ю.И. и его ученики с наиболее общих теоретических позиций показали, что при решении задач распознавания выражениеглобальных (интегральных) свойств объекта через локальные вполне возможно.В настоящее время стало актуальным забытое направление исследований пографодинамике, т.е. исследование графов с изменяемой структурой во времени(темпоральных орграфов (Т-орграфов)).

В графодинамике выделены базовые1Managing and Mining Graph Data. Springer. 2010. 622 pp.http://www.ai.rug.nl/ki2/literature/graphmatch-bunke.pdf4классы задач, связанные с определением равновесного состояния графа и областисходимости к этому состоянию, области циклического изменения состояния графаи длины цикла, расстояния (сходства) между изменяемыми структурами графа,других характеристик. В качестве наиболее значимой выделялась задача определения расстояния, которое помогает ввести представление об устойчивостиизменений структуры графа во времени (графовых траекторий) по отношению кмалым возмущениям и о монотонности в смысле этого расстояния процессов вграфодинамике.

В графодинамике ставятся специфические задачи, которые неимеют аналогов для обычно рассматриваемых объектов. В качестве примеров таких задач выделены:  задача определения в графе подграфа, который не меняетсяили «мало» меняется во времени,  задача о «сохранении коллективов», т.е. выделение группы вершин («коллектива»), которые при изменении структуры графавсегда подчинены общему для них «начальнику». Во всех примерах структураадекватно отображается орграфом или ордеревом.

Появилось большое число работ, в которых отмечено, что в настоящее время одной из актуальных прикладныхзадач является задача анализа изменений во времени структур корпоративныхсоциальных сетей (КCC), в особенности сетей коммуникаций сотрудников фирмы. Структурный анализ КСС позволяет на основе определения сходства структуры Т-орграфа осуществлять мониторинг структуры сети компании, ее изменений и управлять изменениями структуры сети с целью повышения обоснованности принимаемых управленческих решений.

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

Классификация задач определения максимальных общих фрагментов и задач определения сходства двух орграфов с учетом трех видов связности орграфа:слабого, одностороннего, сильного.2. Разработка эффективного алгоритма определения сходства ордеревьев с весами на вершинах и дугах.3. Создание надструктурной характеризации орграфов (Т-орграфов) для решения задач определения сходства орграфов (Т-орграфов) и сходства расположенияих фрагментов с использованием базиса полупутей.54.

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

Доказаны: существование изоморфизма группы автоморфизмов орграфа игруппы автоморфизмов его надграфа для класса орграфов с симметричным отношением смежности вершин, а также существование трех видов связности (слабой,односторонней, сильной) максимальных общих частей (подграфов, фрагментов)пар орграфов любых видов связности.3. Формализована постановка двух классов задач определения сходства Торграфов, позволивших проводить анализ их сходства.4. Предложены и исследованы два подхода к решению задач определениясходства Т-орграфов и исследованию динамики изменения значений сходства наоснове поиска максимальных общих частей двух T-орграфов и максимальной общей части двух полных графов попарного сходства с весами на ребрах на основепостроения системы уточняемых моделей сложности для Т-орграфов.Практическая значимость полученных результатов заключается в созданиимоделей, методов и программных комплексов, позволяющих повысить качество иэффективность решения задач, связанных с определением структурного сходствасистем в приложениях структурной информатики, в разработке ИПС структурнойинформации, в системах искусственного интеллекта с правдоподобными рассуждениями и ИСППР, в системах структурного распознавания образов и др.

Разработанные средства позволяют шире использовать орграфы в теории и практикепрограммирования, компьютерные системы при интеллектуальном анализе сложноорганизованных данных, семантическом web-поиске документов в базах знанийи Интернете и использовать Т-орграфы в анализе изменений административныхструктур, структур снабжения, связи, транспортных структур, различных классовсетей (социальных, биологических, коммуникационных и др.). Результаты работывнедрены в учебный процесс и научно-исследовательскую работу кафедры Прикладной математики ФГБОУ ВО «НИУ МЭИ», в прикладные и научные исследования НИИСИ РАН и использованы в компании ООО «Терминал - Сервис».Методы исследований и достоверность результатов.

Поставленные в работе задачи решались с помощью методов теории графов и прикладной теории графов, теории групп, теории анализа вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др.6Достоверность научных результатов подтверждена теоретическими выкладками, результатами тестирования, а также сравнением полученных результатов с результатами, приведенными в научной литературе.

При обработке сложноорганизованных исходных данных сравнивались результаты, полученные различными методами решения одной и той же задачи.Реализация результатов. Разработанные модели, методы и программныесредства используются в учебном процессе и научно-исследовательской работекафедры Прикладной математики ФГБОУ ВО «НИУ МЭИ», в прикладных инаучных исследованиях НИИСИ РАН, в компании ООО «Терминал - Сервис».

Наразработанный в диссертационной работе программный комплекс получено свидетельство о государственной регистрации программы для ЭВМ в федеральнойслужбе по интеллектуальной собственности.Апробация результатов. Основные результаты работы докладывались и обсуждались на многих международных конференциях и форумах, в том числе: надесятой международной научно-практических конференцияи «Проблемы функционирования информационных систем» (г. Новосибирск, 2008), на 5-й и 6-й азиатских международных школах-семинарах (г. Бишкек, Кыргызская Республика,2009), (г. Усть-Каменогорск, Республика Казахстан, 2010) на 15-й, 16-й, 17-й, 18-ймеждународных научно-технических конференциях студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (г. Москва, 20092012), на международных форумах информатизации МФИ-2009, МФИ-2011,МФИ-2012, МФИ-2014 (международные конференции «Информационные средства и технологии», г.