Содержание к диссертации
Введение
1. Основные подходы к определению сходства графовых моделей систем
1.1. Задачи определения сходства графовых моделей систем и подходы к их решению 16
1.1.1. Подструктурный подход и его развитие 16
1.1.2. Структурно-характеристический подход на основе инвариантов графов 20
1.2. Классификация задач определения максимальных общих частей и сходства двух орграфов 22
1.2.1. Классификация задач определения максимальных общих фрагментов двух орграфов 22
1.2.2. Классификация задач определения сходства орграфов 25
1.3. Результаты вычислительных экспериментов определения сходства орграфов по П-подходу 26
1.3.1. Метод монотонных расширений частичных решений для определения MCS и MCF двух орграфов 26
1.3.2. Результаты анализа П-подхода к определению сходства орграфов и его недостатки 27
1.4. Эффективность решения задач определения сходства на орлесах и ордеревьях 28
1.4.1. Экспериментальные оценки вычислительной сложности алгоритма определения сходства двух ордеревьев по методу монотонных расширений частичных решений 28
1.4.2. Экспериментальные оценки вычислительной сложности оригинального алгоритма определения сходства двух ордеревьев 29
1.5. Задачи вычисления сходства ордеревьев и орлесов, имеющие прикладную значимость 30
1.5.1. Задача вычисления сходства пар ордеревьев и орлесов с весами на вершинах, решаемые по разработанному алгоритму 30
1.5.2. Задача поиска в базе орлесов, сходных с шаблоном 31
1.6. Основные результаты и выводы по главе 35
2. Модели обобщенной надструктурной характеризации орграфов 37
2.1. Обобщенная модель орграфа в базисе полупутей и ее подмодели 38
2.1.1. Порождающая граф-модель орграфа в базисе полупутей 38
2.1.2. Подкласс порождающих граф-моделей орграфа в базисе полупутей
2.2. Стратификация порождающих моделей орграфа в базисе полупутей 45
2.3. Порождающие модели с выделенной вершиной и система методов решения задач определения сходства расположения двух полупутей с уточнением результата
2.3.1. Иерархические g-модели с выделенной вершиной в направленных орграфах 46
2.3.2. Система стратификации g-моделей 48
2.4. Методы решения задач различения и сходства расположения полупутей с учетом их точного расположения в орграфе
2.4.1. Формализованная постановка задачи различения расположения полупутей заданного типа в орграфе
2.4.2. Формализованная постановка задачи определения сходства расположения полупутей в орграфе на основе
2.4.3. Метод решения задачи определения сходства двух орграфов на основе сходства расположения полупутей
2.5. Класс базовых моделей, построенных на основе g-моделей орграфов, и его основные подклассы 52
2.5.1. Класс базовых моделей 53
2.5.2. Примеры решения задач различения орграфов и различения расположения фрагментов в орграфе на основе Ь-моделей 54
2.5.3. Класс иерархических Ь-моделей 56
2.5.4. Система стратификации Ь-моделей 56
2.5.5. Метод количественного определения сходства орграфов с использование Ь-моделей 57
2.5.6. Пример решения задачи определения сходства орграфов на основе Ь-моделей вида V се HPw 58
3. Алгоритмические основы методов надструктурной характеразации для анализа сходства орграфов 62
3.1. Задача определения сходства орграфов и подструктурный подход к её решению 62
3.2. Методы определения сходства орграфов на основе надграфов полупутей
3.2.1. Классификация методов определения сходства двух орграфов 65
3.2.2. Надграфы полупутей как основа нового метода определения сходства орграфов с точной характеризацией
3.2.3. Главное свойство надграфов полупутей 68
3.2.4. Связь изменений надграфов полупутей, порожденных изменениями анализируемых орграфов 73
3.3. Эффективные методы решения задач определения точного и частичного точного сходства орграфов большого
3.3.1. Сведение задачи распознавания изоморфизма надграфов к распознаванию изоморфизма их исходных орграфов 75
3.3.2. Алгоритм конструктивного распознавания исходного орграфа в надграфе полупутей 78
3.3.3. Метод распознавания изоморфизма орграфов большого порядка 80
3.3.4. Метод распознавания изоморфного вложения для орграфов большого порядка 81
3.3.5. Метод определения сходства двух орграфов большого порядка по П-подходу с использованием алгоритма
3.4. Надструктурный подход к определению сходства орграфов 84
3.4.1. Страты надграфов полупутей и их применение для определения сходства орграфов 84
3.4.2. Пример анализа сходства и кластеризации орграфов по П- и Н-подходу 86
3.4.3. Экспериментальные оценки вычислительной сложности алгоритма построения надграфов полупутей для ордеревьев 87
3.4.4. Эффективный алгоритм решения задач определения сходства для двудольных орграфов большого порядка 89
3.5. Результаты экспериментов по определению сходства и различению орграфов на основе характеристик
сходства 89
3.6. Основные результаты и выводы по главе 91
4. Два подхода к определению сходства темпоральных орграфов 94
4.1. Основные определения и базовые классы задач в анализе T-орграфов 95
4.1.1. Основные определения 95
4.1.2. Базовые классы теоретических и прикладных задач в анализе темпоральных орграфов 96
4.2. Два класса задач определения сходства Т-орграфов решению задач 97
4.2.1. Функции вычисления расстояний и индексов сходства структур tiG, tjG 97
4.3. Система методов анализа сходства Т-орграфов по Н-подходу с использованием надграфов полупутей 99
4.4. Метод повышения эффективности решения задач определения сходства темпоральных орграфов 105
4.5. Подход к определению сходства T-орграфов на основе иерархической системы моделей сложности
4.5.1. Расширенная матрица b-модели tG 106
4.5.2. Матрицы вкладов фрагментов в общую сложность tG 107
4.6. Методы анализа глобального и локального сходства двух Т-орграфов 111
4.6.1. Метод анализа глобального сходства T-орграфов на основе индексов и вектор-индексов сложности tG 112
4.6.2. Метод анализа динамики изменения локальных свойств и сходства T-орграфов на основе относительных вкладов вершин в сложность tG 113
4.7. Основные результаты и выводы по главе 114
Заключение 116
Список литературы 118
- Результаты вычислительных экспериментов определения сходства орграфов по П-подходу
- Подкласс порождающих граф-моделей орграфа в базисе полупутей
- Связь изменений надграфов полупутей, порожденных изменениями анализируемых орграфов
- Система методов анализа сходства Т-орграфов по Н-подходу с использованием надграфов полупутей
Введение к работе
Актуальность темы исследования. Графовые модели систем (ГМС) – математические модели структур систем, широко применяемые как в теоретических, так и в прикладных исследованиях. С 2003 года в рамках научного направления DATA MINING активно развивается самостоятельное направление GRAPH MINING с ежегодным обсуждением результатов на международных симпозиумах. В качестве актуальных направлений отмечены исследование вопросов поиска и сравнительного анализа структурной информации, а также получения знаний на основе анализа данных, представленных ГМС. В настоящее время акцент переместился на поиск наиболее близких по сходству структур. Сходство структур систем, являясь ключевым понятием системологии, требует исследований, направленных на создание новых поколений информационно-поисковых систем структурной информации (ИПССИ) (семантический web-поиск), экспертных систем, интеллектуальных систем поддержки принятия решений (ИСППР), на разработку новых подходов в реализации правдоподобных рассуждений, на развитие анализа отношений структурной эквивалентности и толерантности систем (структурная информатика, хим- и био-информатика), на разработку новых подходов в структурном распознавании образов.
Работа продолжает исследования в рамках научной дисциплины – «структурная информатика», теоретической основой которой является «структурный спектральный анализ систем» (СС-анализ), и позволяет на общей теоретико-графовой основе строить эффективные алгоритмы решения базовых задач структурной информатики. Наиболее сложными и значимыми в теоретическом и прикладном аспектах являются задачи определения сходства и кластеризации ГМС1.
В настоящее время задачи анализа сходства остались не исследованными для орграфов, которые являются наиболее общим классом графов, имеющим широкий спектр теоретических и практических применений. Обобщая результаты исследований, которые получили Скоробогатов В.А., Добрынин А.А., Кохов В.А., Грызунов А.Б., Ткаченко С.В., Незнанов А.А., Ибрахим А.Р., Джасим М.Р., Климентовский А.Н., Bunke H., Shearer K., Mekenyan O., Bonchev D. и др., актуальной задачей является разработка общей концепции, объединяющей подструктурную и надструктурную характеризации орграфов и их структурных инвариантов, характеризующих расположение фрагментов, что необходимо для формирования и исследования новых видов отношений структурной эквивалентности и толерантности систем, расширения возможностей и повышения эффективности компьютерных методов анализа сходства ГМС. Проблема анализа сходства орграфов с учетом расположения и сходства расположения фрагментов актуализирована ещё более ввиду того, что Журавлёв Ю.И. и его ученики с наиболее общих теоретических позиций показали, что при решении задач распознавания выражение глобальных (интегральных) свойств объекта через локальные вполне возможно.
В настоящее время стало актуальным забытое направление исследований по графодинамике, т.е. исследование графов с изменяемой структурой во времени (темпоральных орграфов (Т-орграфов)). В графодинамике выделены базовые
1Managing and Mining Graph Data. Springer. 2010. 622 p
классы задач, связанные с определением равновесного состояния графа и области сходимости к этому состоянию, области циклического изменения состояния графа и длины цикла, расстояния (сходства) между изменяемыми структурами графа, других характеристик. В качестве наиболее значимой выделялась задача определения расстояния, которое помогает ввести представление об устойчивости изменений структуры графа во времени (графовых траекторий) по отношению к малым возмущениям и о монотонности в смысле этого расстояния процессов в графодинамике. В графодинамике ставятся специфические задачи, которые не имеют аналогов для обычно рассматриваемых объектов. В качестве примеров таких задач выделены: - задача определения в графе подграфа, который не меняется или «мало» меняется во времени, - задача о «сохранении коллективов», т.е. выделение группы вершин («коллектива»), которые при изменении структуры графа всегда подчинены общему для них «начальнику». Во всех примерах структура адекватно отображается орграфом или ордеревом. Появилось большое число работ, в которых отмечено, что в настоящее время одной из актуальных прикладных задач является задача анализа изменений во времени структур корпоративных социальных сетей (КCC), в особенности сетей коммуникаций сотрудников фирмы. Структурный анализ КСС позволяет на основе определения сходства структуры Т-орграфа осуществлять мониторинг структуры сети компании, ее изменений и управлять изменениями структуры сети с целью повышения обоснованности принимаемых управленческих решений. Управление структурой КСС - новая актуальная область менеджмента.
Таким образом, наиболее актуальной задачей СС-анализа орграфов и Т-орграфов является задача создания общей концепции, включающей подструктурную и надструктурную характеризации орграфов, Т-орграфов и их инвариантов, как новой основы для решения задач определения сходства ГМС.
Объектом исследования являются орграфы и темпоральные орграфы.
Предметом исследования являются модели, методы и программные средства характеризации орграфов и темпоральных орграфов для решения задач определения сходства орграфов и сходства темпоральных орграфов.
Целью диссертационной работы является расширение возможностей и повышение эффективности компьютерных методов анализа сходства ГМС, широкое использование их в научных и прикладных исследованиях, связанных со структурным спектральным анализом систем, таких как ИПССИ, СИИ с правдоподобными рассуждениями, системы структурного распознавания образов, ИСППР, системы семантического web-поиска электронных документов и др.
Для достижения указанной цели в работе решаются следующие задачи:
-
Классификация задач определения максимальных общих фрагментов и задач определения сходства двух орграфов с учетом трех видов связности орграфа: слабого, одностороннего, сильного.
-
Разработка эффективного алгоритма определения сходства ордеревьев с весами на вершинах и дугах.
-
Создание надструктурной характеризации орграфов (Т-орграфов) для решения задач определения сходства орграфов (Т-орграфов) и сходства расположения их фрагментов с использованием базиса полупутей.
-
Разработка метода построения и исследования инвариантов, характеризующих расположение фрагментов в орграфах (Т-орграфах) с использованием расширяемых наборов фрагментов (полупутей).
-
Разработка методов характеризации глобальных и локальных свойств Т-орграфов и решения задач сходства Т-орграфов на основе моделей сложности.
-
Построение программных подсистем «Сходство орграфов», «Сходство темпоральных орграфов» и их использование в учебном процессе и научных исследованиях.
Научная новизна исследований заключается в следующем.
-
Предложены обобщенные модели надструктурной характеризации орграфов и два метода их построения, позволившие получать более точные результаты решения следующих задач: - определения сходства орграфов с учетом как точного, так и приближенного расположения полупутей в орграфах, - определения сходства расположения полупутей в орграфе, - определения сходства орграфов с учетом сходства расположения полупутей в орграфах.
-
Доказаны: существование изоморфизма группы автоморфизмов орграфа и группы автоморфизмов его надграфа для класса орграфов с симметричным отношением смежности вершин, а также существование трех видов связности (слабой, односторонней, сильной) максимальных общих частей (подграфов, фрагментов) пар орграфов любых видов связности.
-
Формализована постановка двух классов задач определения сходства Т-орграфов, позволивших проводить анализ их сходства.
-
Предложены и исследованы два подхода к решению задач определения сходства Т-орграфов и исследованию динамики изменения значений сходства на основе поиска максимальных общих частей двух T-орграфов и максимальной общей части двух полных графов попарного сходства с весами на ребрах на основе построения системы уточняемых моделей сложности для Т-орграфов.
Практическая значимость полученных результатов заключается в создании моделей, методов и программных комплексов, позволяющих повысить качество и эффективность решения задач, связанных с определением структурного сходства систем в приложениях структурной информатики, в разработке ИПС структурной информации, в системах искусственного интеллекта с правдоподобными рассуждениями и ИСППР, в системах структурного распознавания образов и др. Разработанные средства позволяют шире использовать орграфы в теории и практике программирования, компьютерные системы при интеллектуальном анализе слож-ноорганизованных данных, семантическом web-поиске документов в базах знаний и Интернете и использовать Т-орграфы в анализе изменений административных структур, структур снабжения, связи, транспортных структур, различных классов сетей (социальных, биологических, коммуникационных и др.). Результаты работы внедрены в учебный процесс и научно-исследовательскую работу кафедры Прикладной математики ФГБОУ ВО «НИУ МЭИ», в прикладные и научные исследования НИИСИ РАН и использованы в компании ООО «Терминал - Сервис».
Методы исследований и достоверность результатов. Поставленные в работе задачи решались с помощью методов теории графов и прикладной теории графов, теории групп, теории анализа вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др.
Достоверность научных результатов подтверждена теоретическими выкладками, результатами тестирования, а также сравнением полученных результатов с результатами, приведенными в научной литературе. При обработке сложно-организованных исходных данных сравнивались результаты, полученные различными методами решения одной и той же задачи.
Реализация результатов. Разработанные модели, методы и программные средства используются в учебном процессе и научно-исследовательской работе кафедры Прикладной математики ФГБОУ ВО «НИУ МЭИ», в прикладных и научных исследованиях НИИСИ РАН, в компании ООО «Терминал - Сервис». На разработанный в диссертационной работе программный комплекс получено свидетельство о государственной регистрации программы для ЭВМ в федеральной службе по интеллектуальной собственности.
Апробация результатов. Основные результаты работы докладывались и обсуждались на многих международных конференциях и форумах, в том числе: на десятой международной научно-практических конференцияи «Проблемы функционирования информационных систем» (г. Новосибирск, 2008), на 5-й и 6-й азиатских международных школах-семинарах (г. Бишкек, Кыргызская Республика, 2009), (г. Усть-Каменогорск, Республика Казахстан, 2010) на 15-й, 16-й, 17-й, 18-й международных научно-технических конференциях студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (г. Москва, 2009-2012), на международных форумах информатизации МФИ-2009, МФИ-2011, МФИ-2012, МФИ-2014 (международные конференции «Информационные средства и технологии», г. Москва, 2009, 2011, 2012, 2014), на двух международных научно-методических конференциях «Информатизация инженерного образования» Инфорино-2012, Инфорино-2014 (г. Москва, 2012, 2014), на 12-й, 13-й и 14-й национальных конференциях по искусственному интеллекту с международным участием КИИ-2010 (г. Тверь, 2010), КИИ-2012 (г. Белгород, 2012), КИИ-2014 (г. Казань, 2014), на 9-й международной научно-практической конференции «Научное обозрение физ.-мат. и технических наук в XXI веке» (г. Москва, 2014).
Личный вклад диссертанта. Автор диссертация продолжает развитие методов структурного спектрального анализа для решения задач определения сходства ГМС и прошел в составе научной группы весь путь от анализа задач определения сходства графов и ациклических орграфов до создания методологии решения задач и комплексов прикладных программ для определения сходства орграфов, темпоральных орграфов и проведения научных исследований. Наиболее существенный личный вклад автора содержится в разработке классификации задач определения сходства орграфов, в создании обобщенной модели надструктурной характеризации орграфов и двух методов их построения, в формализованной постановке оригинальных классов задач определения сходства Т-орграфов и методов их решения, в разработке двух подходов для решения задач определения сходства и их программную реализацию.
Публикации. Основные результаты исследования опубликованы в 23 печатных работах, из них 5 опубликованы в журналах, входящих в Перечень ВАК РФ.
Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (132 наименования) и приложений. Работа содержит 126 страниц машинописного текста (без приложений).
Результаты вычислительных экспериментов определения сходства орграфов по П-подходу
При анализе сходства ГМС важным является не только сравнение топологических характеристик структур, но и комплексный учёт класса структур, весов вершин и рёбер/дуг, ограничений на расположение и сходство расположения фрагментов и др. В первую очередь актуальной является классификация задач определения сходства с учетом особенностей классов анализируемых ГМС (см. раздел 1.3), что поможет разработать более эффективные алгоритмы анализа сходства и формировать новые виды отношений эквивалентности, толерантности и подобия. В работах [2, 12, 27, 28, 37, 40, 59, 60, 83, 101, 102, 116, 118, 121] рассматриваются четыре подхода к определению структурного сходства ГМС: 1) подструктурный подход (П-подход), 2) расширенный П-подход, 3) обобщенный П-подход на основе использования надграфов, характеризующих расположение фрагментов в ГМС, 4) структурно-характеристический подход (СХ-подход) на основе использования моделей сложности (инвариантов) ГМС.
Подструктурный подход и его развитие Будем говорить, что сформулирована классическая задача определения сходства орграфов, если заданы следующие параметры: . 9l={G1,G2,…,Gw} - множество орграфов; . D(Gi,Gj) - значение расстояния между орграфами Gt и G; . SI(Gi,Gj) - значение индекса сходства G, Gj. Необходимо построить матрицу (граф) попарных расстояний между парами орграфов или матрицу коэффициентов (граф) попарного сходства.
Таким образом, задача определения сходства на множестве орграфов УІ определена, если задана тройка параметров: SIM = (SR, D, SI). Под результатом решения задачи определения сходства набора из п орграфов будем понимать полный граф с п вершинами, каждое ребро которого {v,-,v,-} взвешено значением расстояния D{Gi ,G}) (индекса сходства SI{Gt ,G})).
Диапазон изменения и разнообразие значений расстояний существенно влияют на возможность решения задачи кластеризации анализируемых орграфов и на результаты кластеризации. Чем шире разнообразие значений, тем больше возможностей для решения задачи кластеризации и получения результатов, которые интересуют исследователя.
Концепция П-подхода базируется на использовании максимальных общих фрагментов двух графов. Пусть 93 обозначает множество графов, определенных с точностью до изоморфизма.
Подграфовая метрика: D . 93 X 93 - К0, где К0 - множество неотрицательных целых чисел, определена через D G,H) =min{\G\ + \Н\ — 2С), где минимум берется по всем графам С, которые являются подграфами и в графе G, и в графе Я, а G, Яє 93 2. Таким образом, величина сходства зависит от размера (числа вершин и/или ребер) максимального общего фрагмента (MCF) анализируемых графов. Меры расстояния ( ), индексы сходства (SI) и несходства (DSI) Gx и G2 вычисляются по формулам3:
Однако, до сих пор не разработаны алгоритмы для исследования и применения возможностей П-подхода при анализе орграфов. Расширение П-подхода повышает его различительную способность, но увеличивает как временную, так и емкостную вычислительную сложность. Основная суть РП-подхода заключается в использовании информации обо всех максимальных общих фрагментах (МОФ) ГМС и учете их сложности. Результаты исследования РП-подхода при исследовании ациклических структур, состоящих из орграфов без контуров и деревьев, приведены в [19].
ОП-подход в применении к учету сходства расположения фрагментов в графах предложен в [25]. Основная его суть заключается в использовании граф-моделей (gso-моделей), позволяющих точно охарактеризовать расположение фрагментов в ГМС и на этой основе определять сходство ГМС с учетом сходства расположения фрагментов. На рис. 1.2 приведены примеры gs- и gso-моделей, характеризующих сходство расположения подграфов C3 и C4, и орбитами подграфов в графе G. ОП-подход выполняется в два этапа. Сначала определяется сходство расположения фрагментов, которые интересуют исследователя, а затем сходство ГМС с учетом сходства расположения фрагментов на основе определения МОФ построенных gso-моделей (рис. 1.3). Результаты программной реализации ОП-подхода для обыкновенных графов и исследования эффективности его применения приведены в [41, 44, 45, 61]. Главная отличительная особенность ОП-подхода состоит в том, что он позволяет решать новый класс задач – задач определения сходства расположения фрагментов при точной характеризации их расположения.
Расширение возможностей применения ОП-подхода, связанное с учетом информации о сходстве расположения полупутей при точной характеризации их расположения в ордеревьях общего вида, предложено автором в [50]. Ниже под ордеревом общего вида понимаем связный орграф, в котором между каждой парой вершин существует только один простой полупуть.
Подкласс порождающих граф-моделей орграфа в базисе полупутей
Если в g-модели [ЯР и/ с HPlw\ не рассматривать структурные веса вершин, то будет выделен подкласс скелетных g-моделей, которые обозначим [SHPlQHPl\. С целью дальнейшего введения моделей и повышения эффективности их построения выделим подкласс иерархических скелетных g-моделей, которые обозначим как [HSHP1 Q НР1\, а при вложении как концевого фрагмента - через [HSHP1 Яе НР1\.
Утверждение 2.1. g-модель [SHPlwlQHPlwl\ задает орграф G с точностью до изоморфизма. Доказательство. Действительно, рассмотрим в матрице g-модели [SHPlwl с HPlwl\ орграфа G подматрицу [SHP&w1 Q HP[wl\ = [Vі с El\. Данная подматрица является матрицей инцидентностей «вершины-дуги», которая и задает орграф с точностью до изоморфизма. Следствие. На основе g-модели вида [SHPlwl Ш HPlwl\ орграф G восстанавливается с точностью до изоморфизма.
Утверждение 2.2. g-модель [HSHPlw С HPlwl\ задает орграф G с точностью до изоморфизма.
Следствие. На основе g-модели вида [HSHPlw Q HPlwl\ орграф G восстанавливается с точностью до изоморфизма.
Пример иерархической скелетной g-модели [HSHP1 Щ орграфа G (рис. 2.1) приведен на рис. 2.2 (А). На рис. 2.2 (В) показан вид цветной иерархической скелетной g-модели [cHSHP1 Щ, в которой цвет вершин (уровень расположения вершин) соответствует полупутям определенной длины (длина 0 (нет цвета), длина 1 (цвет желтый), длина 2 (цвет красный), длина 3 (цвет зеленый)). 11 #.12 «13 2 отношение Aut{G) « Aut([cHSHPl Ш (G)J). Следовательно, все вершины g-модели [cHSHP1 я\ взаимно-однозначно соответствуют всем полупутям и сохраняют симметрию их расположения в орграфе G, то есть точно характеризуют расположение полупутей в G. g-Модели [cHSHP1 Щ и [HSHP1 Щ являются структурными инвариантами G. Использование их в П-подходе определения сходства двух орграфов приводит к выделению нового подхода - надструктурного (Н-подхода), учитывающего сходство расположения полупутей при характеризации последних с точностью до орбит групп от AuthPo (G) до Authnv-V (G).
Выделим параметры стратификации: 1) вид вложения полупутей (как фрагмент (с), как подграф (Qs)), 2) учет или неучет структурных весов (wL,wR) вершин g-модели, 3) учет или неучет иерархии (Я) вложения полупутей, 4) вид изоморфного вложения одного полупути в другой (как концевой фрагмент (Ше), как любой фрагмент).
Многообразие тех подклассов g-моделей и их страт, которые являются инвариантами орграфа, приводит к выделению многообразия методов Н-подхода при определении сходства орграфов. На основе выделения одного фрагмента и учета орбит группы автоморфного расположения полупутей можно выделять новые виды моделей для исследования и для их применения при решении задач различения и определения сходства расположения полупутей.
Порождающие модели с выделенной вершиной и система методов решения задач определения сходства расположения двух полупутей с уточнением результата
Иерархические g-модели с выделенной вершиной в направленных орграфах Рассмотрим подмножество вершин левой доли g-модели [HPlwl Щ, в структурные веса которых входит выделенный фрагмент. Начнем рассмотрение вида g-моделей с выделенным фрагментом-вершиной, который обозначим через [HPlvwlQ\. Пусть finv fimv обозначает, что фрагмент ftlnv с выделенной вершиной v достраивается до фрагмента f-mv, включающего вершину v в орграфе G. В соответствии с выделением двух видов достройки фрагмента flnv до f}mv (до подграфа орграфа (S), до фрагмента (F)) и двух видов вхождения вершины в фрагмент (как висячая-концевая (е), как произвольное вхождение) будем различать четыре основных вида g-моделей: [HPlvwl Ше\, [HPlvwl QeS\, [HPlvwl Ш\, [HPlvwl Щ.
Определение 2.3. Матрицей смежности g-модели [HHPlvwl Qe\ орграфа G называется матрица [M_HHPlvwl Ше\ = wim, n,mEl..k, для которой wim = 1, если flnv се f}mv и т=п+1, и wlnm = 0 в любом другом случае.
На рис. 2.3 приведена g-модель с выделенной вершиной 1 и соответствующая ей матрица [M_HHPlvwl Qe\ для G (рис. 2.1), а также g-модели вида [HHPlvwlQe\и[HHPlvwQe\.
Удалением из рассмотрения пометок у весов вершин построим структурные иерархические модели, которые являются инвариантами, характеризующими расположение вершин в орграфе. №123 45 w l w 4
Матричный вид g-модели [HHPlvwl Qe\ и примеры двух g-моделей ({HHPlvwlQel[HHPlvwQe\). Определение 2.4. Набор g-моделей [HPlvwl Ше\, построенных поочередно для каждой вершины орграфа G, называется S-спектром орграфа относительно [HPlvwQe\, а набор попарно неизоморфных g-моделей [HPlvw Яе\ называется -спектром орграфа относительно [HPlvw Ше\. Пример инвариантов вершин (5 -спектра орграфа G (рис. 2.1) и 5 -спектра орграфа (рис. 2.1 с заменой дуги (12) на (21)) относительно [HPlvw Яе\ показан на рис. 2.4. Рассмотренный вид моделей для полупутей длины 0 легко обобщается на полупути любого вида.
При удалении из [HPlvw Ше\ структурных весов w получим, в общем случае с потерей точности характеризации, более простые структурные иерархические модели, сохраняющие информацию о длине полупутей и являющиеся инвариантами, характеризующими расположение полупутей в орграфе.
Связь изменений надграфов полупутей, порожденных изменениями анализируемых орграфов
В П3 приведены ЭОВС алгоритмов построения НПП для планарных орграфов средней сложности (полином второй степени при анализе полупутей пяти типов и полином пятой степени при анализе полупутей 19 типов) и случайных орграфов с плотностью заполнения матриц инцидентности 8% (полином четвертой степени при анализе полупутей пяти типов и полином пятой степени при анализе полупутей 19 типов).
Пусть Ш обозначает множество всех связных орграфов и пусть построены группы автоморфизмов Aut(G1), Aut(G2) орграфов G1, G2 и пусть ДО , Q(G2) обозначают, соответственно, множества всех автоморфизмов из Aut(G1), Aut(G2). Пусть gogkEQiGi). Графы G1 и G2 имеют изоморфные группы (Aut(Gi) Aut{G2)\ если существует отображение h: g(G±) Q(G2\ для которого выполняется следующее условие: (Увивк Є GiG Qifa дк) = Кд[) h{gk)).
Простые полупути в G обладают тем важным свойством, что полупуть с длиной к может быть представлен «склейкой» двух полупутей длины (к-\). Точнее, если в G присутствует полупуть (v0,v1,... ,vk), то можно считать его образованным полупутями (v0tvlt..., vfc_i) и (vltv2 ...,vk). С другой стороны, в случае присутствия в графе полупутей (v0 vlt..., vk_t) и (v1; v2,..., vk) существует фрагмент (v0tvlt...tvk-ltvk), являющийся либо полупутем, либо замкнутым полупутем (когда v0 = V/). Это позволяет последовательно, начиная с полупутей длины 1, добавлять к строящемуся надграфу вершины и соединять их ребром тогда и только тогда, когда соответствующие этим вершинам полупути могут быть «склеены» с образованием нового простого полупути. Процесс «склейки» остановится, так как на некотором шаге станет невозможно соединить рёбрами вновь добавленные вершины, что свидетельствует о построении на предыдущем шаге простых полупутей максимальной для анализируемого G длины. Таким образом, каждый полупуть взаимнооднозначно отображается вершиной сghp(G). Так как операция 1-гомеоморфного расширения является инвариантной относительно Aut(G) операцией, то есть добавление одной вершины на каждой дуге является инвариантной относительно Aut(G), поскольку новые автоморфизмы не появятся из-за цвета новых вершин, отличного от цвета вершин исходного G. Новые вершины взаимно-однозначно соответствуют дугам исходного G и не приводят к изменению симметрии расположения анализируемых полупутей на каждом шаге построения сghp{G).
Приведенные рассуждения и результаты ОВЭ по построению и сравнению на изоморфизм групп орграфов (табл. 3.2) с группами автоморфизмов вершин их cghp(G), cghp–(G), ghp(G), ghp\G) привели к формулировке следующих гипотез.
Надграфы gA/T(G) образуют подкласс класса -дольных орграфов с рядом особенностей. Число долей (ярусов) к определяется длиной максимального полупути в G. Каждая вершина, расположенная на ярусе у 0, инцидентна двум дугам с предыдущего яруса. Пусть Ш а Ш обозначает множество всех связных орграфов с симметричным бинарным отношением смежности вершин. Тогда полупути в G Є 9Л становятся цепями, алгоритм построения НПП упрощается до алгоритма, приведенного в [78], и справедливо следующее утверждение для p(G)
Доказательство. Рассмотрим орграф G еШ с числом вершин более четырех. В соответствии с изложенным выше алгоритмом, построим cgp{G) для цепей длины 1. Операция 1-гомеоморфного расширения исходного G, то есть добавления одной вершины на каждом ребре, является инвариантной относительно Aut(G), поскольку новые автоморфизмы не появятся из-за цвета новых вершин, отличного от цвета вершин исходного G. Новые вершины взаимно-однозначно соответствуют ребрам G и не приводят к изменению симметрии исходного G в силу справедливости теоремы Уитни-Юнга о распространении реберного изоморфизма графов на вершинный. Выполним шаг 3 алгоритма, то есть каждую пару новых вершин v,Vj, взаимно-однозначно соответствующих рёбрам исходного G, соединим новым ребром {v,Vy}, если Г гГїГ у 0. В результате получим на множестве новых вершин (вершин с номером цвета 1) орграф G , который является реберным графом к исходному G (пример на рис. 1), и, в силу справедливости теоремы Уитни-Юнга, выполненная достройка является инвариантной относительно Aut(G). Так как при выполнении алгоритма на каждом его этапе, включающем повторение шагов 2 и 3, строится новая часть модели, однозначно соответствующая части реберного орграфа, построенной на предыдущем этапе, и эта достройка инвариантна относительно Aut(G), то в результате построения всего cgp(G) инвариантность достройки относительно Aut(G) сохраняется, так как она сохраняется на каждом этапе построения.
Система методов анализа сходства Т-орграфов по Н-подходу с использованием надграфов полупутей
В настоящее время актуальным направлением исследований является разработка методов анализа орграфов с изменяемой структурой во времени (темпоральных орграфов, далее Т-орграфов) [1, 5, 81, 96]. Работа [1] - одна из первых по графодинамике, т.е. по динамическому описанию структур. В связи с расширением сфер практической применимости, в особенности, при разработке новых поколений систем поддержки принятия решений, систем искусственного интеллекта и при анализе темпоральных сетей10 (компьютерных, социальных, коммуникационных и др.) c 2006 года активно развиваются исследования по графодинамике11 [77, 80, 90, 91, 95, 96, 103, 105, 106, 114, 115, 119, 125, 126]. Однако, область исследования Т-орграфов еще недостаточно раскрыта в современной научной литературе.
В данной главе с целью решения одной из центральных проблем графодинамики - проблемы определения расстояния, которое помогает ввести представление об устойчивости изменений структуры Т-орграфов во времени (графовых траекторий) и о монотонности в смысле этого расстояния - выделены два класса задач анализа сходства и предложены два подхода: обобщенный П-подход, включающий 4 метода и подход на основе системы уточняемых моделей сложности, обобщенных для применения к орграфам.
С целью многостороннего исследования сходства T-орграфов в работе предложены 28 видов задач, составляющих класс центральных задач графодинамики. Предложены методы, включающие построение и сравнение оригинальных инвариантов T-орграфов (матриц достроек вершин до полупутей
Затуливетер Ю.C., Фищенко Е.А. Графодинамические системы с сетецентрическим управлением в математически однородном поле компьютерной информации // Управление большими системами: сборник трудов: Сетевые модели в управлении. ИПУ РАН. 2010. № 30-1. С. 567-604.
Holme P., Samaraki J. Temporal networks. Physics reports. 19. 2012. P. 97-125. заданных длин), с целью повышения эффективности решения задач на основе перехода от труднорешаемых задач определения максимальных общих частей двух Г-орграфов к полиномиальным по вычислительной сложности алгоритмам определения сходства Г-орграфов на основе инвариантов Г-орграфов.
Для выявления монотонности изменения структур Г-орграфов предложены оригинальные характеристики определения расстояния (индексов сходства) между парой Г-орграфов или между структурами одного Г-орграфа.
Тройку G = (V \E \T) назовем Г-орграфом, где V&- множество вершин орграфа в момент времени t с числом вершин \V \ = р \ Т = 1.. N -множество натуральных чисел, определяющих (дискретное) время, Е- семейство соответствий или отображений Гс Є E(t) множества вершин \ в себя в момент времени t Є Т. Через tG обозначим Г-орграф в момент времени t. При удалении вершин и смежных с ними дуг в tG получаем его подграф, а при удалении одной или нескольких дуг получаем фрагмент/ Орграф ttG = К(Ч Е(Ч Т) изоморфен орграфу t2G = (V \E \T) (обозначается t±G « t2G), если существует отображение р:уЫ- У«2, такое, что
(yvuvj Є V )((vuvj) Є ЕЫ { p{vd, p{Vj)) Є (t2)) где (p(Vi),(p(Vj)EV \ Множество всех изоморфизмов tG на себя образует группу AutitG). Орграф t±G = (V \E ,T) изоморфно вкладывается в орграф t2G = (V \E \T) как фрагмент, если в t2G есть фрагмент / « ttG. Если фрагмент /является подграфом в t2G, то примем обозначение ttGQs t2G. Под максимальным общим подграфом MCS (фрагментом (MCF)) для txG, t2G понимаем фрагмент /1 = tli2G = (V \E \T), для которого справедливы два условия: a) tli2G Qs ttG (соответственно, t1 2G Ш ttG) и t1 2G Qs t2G (соответственно, tli2G с t2G), b) не существует большего по числу вершин (дуг) фрагмента f1,2G в t1G, для которого выполняется условие а.
Отличие Г-орграфов от орграфов связано с необязательностью выполнения свойства транзитивности по пути.
На рис. 4.1 приведены два Г-орграфа TG1, TG2 в трех вариантах представления, а также их MCS(hG,…,UG). Задача поиска MCS(t1G,…,t4G) (MCF(hG,…,hG)) имеет самостоятельное значение и является одной из центральных задач графодинамики - определения подграфа (фрагмента), который не меняется или «мало» меняется во времени.
В [1] выделены центральные проблемы графодинамики, связанные с определениями равновесного состояния Т-графа и области сходимости к этому состоянию, области циклического изменения состояния Т-графа и длины цикла, расстояния (сходства) между изменяемыми структурами Т-графа и др. В качестве наиболее значимой выделена задача определения расстояния, которое помогает ввести представление об устойчивости изменений структур Т-орграфа во времени (графовых траекторий) и о монотонности в смысле этого расстояния процессов в графодинамике. Примерами прикладных задач являются анализ изменений административных структур, обычно описываемых ордеревьями, организации систем связи, снабжения и др., структуры построения номенклатуры товаров или изделий определенной категории, организации ассоциативной памяти ЭВМ. В графодинамике ставятся специфические задачи, которые не имеют аналогов в динамике обычно рассматриваемых объектов. В [1] в качестве примеров таких задач особо выделены: - задача определения в графе подграфа, который не меняется или «мало» меняется во времени, - задача о «сохранении коллективов», т.е. выделение вершин («коллектива»), которые при изменении структуры графа всегда подчинены общему для них «начальнику».
Во всех примерах структура адекватно отображается орграфом. В [80, 96, 119, 105, 115, 126] отмечено, что в настоящее время одной из актуальных прикладных задач является задача анализа изменений во времени структур корпоративных социальных сетей (КCC), в особенности сетей коммуникаций сотрудников фирмы. Структурный анализ КСС позволяет осуществлять мониторинг структуры сети компании и ее изменений, выявлять слабых и сильных акторов в сети, корректировать и моделировать эффективную структуру сети, оперативно выявлять конфликты акторов внутри фирмы, анализировать создание сообществ по формальным и неформальным связям, что способствует созданию единой команды с общей целью, направлять изменения структуры сети с целью повышения обоснованности управленческих решений. Управление КСС и их структурой - новая область менеджмента [119].