Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Кохов Виктор Викторович

• Кохов Виктор Викторович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Кохов Виктор Викторович

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

1. ОСНОВНЫЕ ПОДХОДЫ К ОПРЕДЕЛЕНИЮ СХОДСТВА ГРАФОВЫХ МОДЕЛЕЙ СИСТЕМ

1.1. Задачи определения сходства графовых моделей систем и подходы к их решению

1.1.1. Подструктурный подход и его развитие

1.1.2. Структурно-характеристический подход на основе инвариантов графов

1.2. Классификация задач определения максимальных общих частей и сходства двух орграфов

1.2.1. Классификация задач определения максимальных общих фрагментов двух орграфов

1.2.2. Классификация задач определения сходства орграфов

1.3. Результаты вычислительных экспериментов определения сходства орграфов по П-подходу

1.3.1. Метод монотонных расширений частичных решений для определения МСБ и МСГ двух орграфов

1.3.2. Результаты анализа П-подхода к определению сходства орграфов и его недостатки

1.4. Эффективность решения задач определения сходства на орлесах и ордеревьях

1.4.1. Экспериментальные оценки вычислительной сложности алгоритма определения сходства двух ордеревьев по методу монотонных расширений частичных решений

1.4.2. Экспериментальные оценки вычислительной сложности оригинального алгоритма определения сходства двух ордеревьев

1.5. Задачи вычисления сходства ордеревьев и орлесов, имеющие прикладную значимость

1.5.1. Задача вычисления сходства пар ордеревьев и орлесов с весами на вершинах, решаемые по разработанному алгоритму

1.5.2. Задача поиска в базе орлесов, сходных с шаблоном

1.6. Основные результаты и выводы по главе

2. МОДЕЛИ ОБОБЩЕННОЙ НАДСТРУКТУРНОЙ ХАРАКТЕРИЗАЦИИ ОРГРАФОВ

2.1. Обобщенная модель орграфа в базисе полупутей и ее подмодели

2.1.1. Порождающая граф-модель орграфа в базисе полупутей

2.1.2. Подкласс порождающих граф-моделей орграфа в базисе полупутей

2.2. Стратификация порождающих моделей орграфа в базисе полупутей

2.3. Порождающие модели с выделенной вершиной и система методов решения задач определения сходства расположения двух полупутей с уточнением результата

2.3.1. Иерархические д-модели с выделенной вершиной в направленных орграфах

2.3.2. Система стратификации д-моделей

2.4. Методы решения задач различения и сходства расположения полупутей с учетом их точного расположения в орграфе

2.4.1. Формализованная постановка задачи различения расположения полупутей заданного типа в орграфе и пример решения задачи

2.4.2. Формализованная постановка задачи определения сходства расположения полупутей в орграфе на основе структурных инвариантов

2.4.3. Метод решения задачи определения сходства двух орграфов на основе сходства расположения полупутей

2.5. Класс базовых моделей, построенных на основе g-моделей орграфов, и его основные подклассы

2.5.1. Класс базовых моделей

2.5.2. Примеры решения задач различения орграфов и различения расположения фрагментов в орграфе на основе b-моделей

2.5.3. Класс иерархических b-моделей

2.5.4. Система стратификации b-моделей

2.5.5. Метод количественного определения сходства орграфов с использование b-моделей

2.5.6. Пример решения задачи определения сходства орграфов на основе b-моделей вида V £е HPw

2.6. Основные результаты и выводы по главе

3. АЛГОРИТМИЧЕСКИЕ ОСНОВЫ МЕТОДОВ НАДСТРУКТУРНОЙ ХАРАКТЕРАЗАЦИИ ДЛЯ АНАЛИЗА СХОДСТВА ОРГРАФОВ

3.1. Задача определения сходства орграфов и подструктурный подход к её решению

3.2. Методы определения сходства орграфов на основе надграфов полупутей

3.2.1. Классификация методов определения сходства двух орграфов

3.2.2. Надграфы полупутей как основа нового метода определения сходства орграфов с точной характеризацией расположения фрагментов в орграфе

3.2.3. Главное свойство надграфов полупутей

3.2.4. Связь изменений надграфов полупутей, порожденных изменениями анализируемых орграфов

3.3. Эффективные методы решения задач определения точного и частичного точного сходства орграфов большого порядка

3.3.1. Сведение задачи распознавания изоморфизма надграфов к распознаванию изоморфизма их исходных орграфов

3.3.2. Алгоритм конструктивного распознавания исходного орграфа в надграфе полупутей

3.3.3. Метод распознавания изоморфизма орграфов большого порядка

3.3.4. Метод распознавания изоморфного вложения для орграфов большого порядка

3.3.5. Метод определения сходства двух орграфов большого порядка по П-подходу с использованием алгоритма свертки надграфов полупутей

3.4. Надструктурный подход к определению сходства орграфов

3.4.1. Страты надграфов полупутей и их применение для определения сходства орграфов

3.4.2. Пример анализа сходства и кластеризации орграфов по П- и Н-подходу

3.4.3. Экспериментальные оценки вычислительной сложности алгоритма построения надграфов полупутей для ордеревьев

3.4.4. Эффективный алгоритм решения задач определения сходства для двудольных орграфов большого порядка

3.5. Результаты экспериментов по определению сходства и различению орграфов на основе характеристик сходства

3

Основные результаты и выводы по главе

91

4. ДВА ПОДХОДА К ОПРЕДЕЛЕНИЮ СХОДСТВА ТЕМПОРАЛЬНЫХ ОРГРАФОВ

4.1. Основные определения и базовые классы задач в анализе T-орграфов

4.1.1. Основные определения

4.1.2. Базовые классы теоретических и прикладных задач в анализе темпоральных орграфов

4.2. Два класса задач определения сходства Т-орграфов решению задач

4.2.1. Функции вычисления расстояний и индексов сходства структур tfi, tjG

4.3. Система методов анализа сходства Т-орграфов по Н-подходу с использованием надграфов полупутей

4.4. Метод повышения эффективности решения задач определения сходства темпоральных орграфов

4.5. Подход к определению сходства T-орграфов на основе иерархической системы моделей сложности

4.5.1. Расширенная матрица b-модели tG

4.5.2. Матрицы вкладов фрагментов в общую сложность tG

4.6. Методы анализа глобального и локального сходства двух Т-орграфов

4.6.1. Метод анализа глобального сходства T-орграфов на основе индексов и вектор-индексов сложности tG

4.6.2. Метод анализа динамики изменения локальных свойств и сходства T-орграфов на основе относительных вкладов вершин в сложность tG

4.7. Основные результаты и выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1. ОБОСНОВАНИЕ СПРАВЕДЛИВОСТИ УТВЕРЖДЕНИЯ

ПРИЛОЖЕНИЕ 2. АЛГОРИТМ ОПРЕДЕЛЕНИЯ СХОДСТВА ОРДЕРЕВЬЕВ И ОБОСНОВАНИЕ ПОЛИНОМИАЛЬНОСТИ АЛГОРИТМА

ПРИЛОЖЕНИЕ 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ОЦЕНКИ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ

ПРИЛОЖЕНИЕ 4. РАЗРАБОТАННЫЕ ПРОГРАММНЫЕ КОМПЛЕКСЫ И ИХ ПРИМЕНЕНИЕ

ПРИЛОЖЕНИЕ 5. КОПИИ АКТОВ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ

список сокращений

1. АС - Ациклическая структура.

2. АСНИ - Автоматизированная система научных исследований.

3. БД - База данных.

4. ГМС - Графовая модель системы.

5. ИПССИ - Информационно-поисковая система структурной информации.

6. ИСППР - Интеллектуальная система поддержки принятия решений.

7. КИИ - Конференция по искусственному интеллекту.

8. КЭВ - Класс эквивалентности вершин.

9. КСС - Корпоративная социальная сеть.

10. MCS - Maximum common subgraph.

11. MCF - Maximum common fragment.

12. ММРЧР - Метод монотонных расширений частичных решений.

13. МОФ - Максимальный общий фрагмент.

14. Н-подход - Надструктурный подход.

15. НПП - Надграф полупутей.

16. ОВЭ - Объемные вычислительные эксперименты.

17. ОГ - Ориентированный граф.

18. ОП-подход - Обобщенный подструктурный подход.

19. П-подход - Подструктурный подход.

20. ПСС - Полный структурный спектр.

21. РП-подход - Расширенный подструктурный подход.

22. СД - Структурный дескриптор.

23. СХ-подход - Структурно-характеристический подход.

24. СИИ - Система искусственного интеллекта.

25. СС-анализ - Структурный спектральный анализ.

26. ЭС - Экспертная система.

27. ЭОВС - Экспериментальная оценка вычислительной сложности.

Введение диссертации (часть автореферата) на тему «Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов»

введение

Тема работы: модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов. Актуальность темы работы

Графовые модели систем (ГМС) - математические модели структур систем, широко применяемые как в теоретических, так и в прикладных исследованиях [21, 62]. С 2003 года в рамках научного направления DATA MINING выделено и активно развивается самостоятельное направление GRAPH MINING с ежегодным обсуждением результатов на международных симпозиумах [74, 89, 113]. В качестве актуальных направлений выделено исследование вопросов поиска и сравнительного анализа структурной информации, а также получения знаний на основе анализа данных, представленных ГМС. В настоящее время акцент переместился на поиск наиболее близких по сходству структур. Сходство структур систем, будучи ключевым понятием системологии, требует наиболее общих исследований, направленных на 1) создание новых поколений информационно-поисковых систем структурной информации (ИПССИ) (семантический we^-поиск), систем искусственного интеллекта (СИИ), экспертных систем (ЭС), интеллектуальных систем поддержки принятия решений (ИСППР) [29, 43, 129], 2) разработку новых подходов в реализации правдоподобных рассуждений [54, 70], 3) развитие анализа отношений структурной толерантности систем (структурная информатика, хим- и биоинформатика и др. [19,75], 4) разработку новых подходов в структурном распознавании образов [104, 9, 127].

Таким образом, в качестве центральной проблемы сравнительного анализа структурной информации выделена проблема анализа сходства ГМС и в первую очередь орграфов, как наиболее общего случая графов.

Работа продолжает исследования в рамках научной дисциплины -«структурная информатика», теоретической основой которой является «структурный спектральный анализ систем» (СС-анализ) [30, 31, 46, 48], и

позволяет на единой теоретико-графовой основе строить эффективные алгоритмы решения базовых задач структурной информатики. В СС-анализе выделены 7 классов задач [46, 48]: 1) характеризация структур на основе порождающих и базовых граф-моделей в расширяемых базисах структурных дескрипторов (СД), 2) сравнительный анализ структур, 3) сравнительный анализ расположения фрагментов в структурах, 4) обобщенный СЕА-анализ, 5) генерация и конструктивное перечисление структур; 6) прорисовка диаграмм структур, 7) разработка методов визуализации процесса поиска решения и их использование в интерактивных системах программирования.

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

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

Обычно модели и методы теории графов используются для анализа отношений между элементами сложных структур различной природы. При этом данные отношения между элементами не меняются во времени. Такие графы в [1] названы «статическими». Как отмечено в [5, 81, 83] в настоящее время наиболее актуальным направлением является разработка методов анализа графов с изменяемой структурой во времени (темпоральных орграфов (Г-орграфов)). Работа [1] была началом исследований по описанию динамических структур. В ней выделены базовые классы задач, связанные с определением 1) равновесного

состояния графа и области сходимости к этому состоянию, 2) области циклического изменения состояния графа и длины цикла, 3) расстояния (сходства) между изменяемыми структурами графа и других характеристик. В качестве наиболее значимой выделялась задача определения расстояния, которое помогает ввести представление об устойчивости изменений структуры графа во времени (графовых траекторий) по отношению к малым возмущениям и о монотонности в смысле этого расстояния процессов в графодинамике. Примерами прикладных задач является анализ изменений 1) административных структур, обычно описываемых орграфами-деревьями, 2) организации систем связи, снабжения и др., 3) структуры построения номенклатуры товаров или изделий определенной категории, 4) организации ассоциативной памяти ЭВМ и др. В графодинамике ставятся специфические задачи, которые не имеют аналогов для обычно рассматриваемых объектов. В [1] в качестве примеров таких задач выделены: 1) задача определения в графе подграфа, который не меняется или «мало» меняется во времени, 2) задача о «сохранении коллективов», т.е. выделение группы вершин («коллектива»), которые при изменении структуры графа всегда подчинены общему для них «начальнику». Во всех примерах структура адекватно отображается орграфом. В [5, 96] отмечено, что в настоящее время одной из актуальных прикладных задач является задача анализа изменений во времени структур корпоративных социальных сетей (КСС), в особенности сетей коммуникаций сотрудников фирмы. Структурный анализ КСС позволяет на основе определения сходства структуры Г-орграфа в любой момент времени по отношению к началу интервала анализируемого времени осуществлять мониторинг структуры сети компании, ее изменений и управлять изменениями структуры сети с целью повышения обоснованности принимаемых управленческих решений. Как показано в [96], управление структурой КСС - новая актуальная область менеджмента.

Таким образом, наиболее актуальными задачами СС-анализа орграфов и Г-орграфов является задача создания единой концепции, включающей

подструктурную и надструктурную характеризации орграфов, Г-орграфов и их инвариантов, как новой основы для решения задач определения сходства.

Основные определения, связанные с орграфами и их группами автоморфизмов можно найти в [21, 62]. Цель работы

Цель диссертационной работы - расширить возможности и повысить эффективность компьютерных методов анализа сходства ГМС, широко использовать их в научных и прикладных исследованиях, связанных со структурным спектральным анализом систем, таких как ИПССИ, СИИ с правдоподобными рассуждениями, системы структурного распознавания образов, ИСППР, системы семантического web-поискa электронных документов и др.

Для достижения цели необходимо создание надструктурной характеризации орграфов и Г-орграфов, обобщающей подструктурную характеризацию и ее программной реализации для решения задач определения сходства орграфов, Г-орграфов и сходства расположения их фрагментов. Решаемые задачи

1. Классификация задач определения максимальных общих фрагментов и задач определения сходства двух орграфов с учетом трех видов связности орграфа: слабого, одностороннего, сильного.

2. Разработка эффективного алгоритма определения сходства ордеревьев (орлесов) с весами на вершинах и дугах.

3. Создание надструктурной характеризации орграфов (Г-орграфов) для решения задач определения сходства орграфов (Г-орграфов) и сходства расположения их фрагментов с использованием базиса полупутей.

4. Разработка метода построения и исследования инвариантов, характеризующих расположение фрагментов в орграфах (Г-орграфах) с использованием расширяемых наборов структурных дескрипторов (полупутей).

5. Разработка методов характеризации глобальных и локальных свойств Г-орграфов и решения задач анализа сходства Г-орграфов на основе моделей сложности.

6. Построение программных комплексов «Сходство орграфов», «Сходство темпоральных орграфов» и их использование в учебном процессе и научных исследованиях.

Научная новизна

Новыми научными результатами являются:

1. Обобщенные модели надструктурной характеризации орграфов и метод их построения, позволившие получать более точные результаты решения задач определения сходства орграфов с учетом как точного, так и приближенного расположения полупутей в орграфах, определения сходства расположения полупутей в орграфе, определения сходства орграфов с учетом сходства расположения полупутей в орграфах.

2. Доказательство существования пар орграфов любых видов связности, МС8 которых может быть любого заданного вида связности: слабого, одностороннего, сильного.

3. Формализованные постановки двух оригинальных классов задач определения сходства Г-орграфов, позволившие проводить многосторонний анализ их сходства и решать две центральные задачи графодинамики: определение расстояния между изменяемыми структурами Г-орграфа, а также определение областей циклического изменения структур Г-орграфа и длины цикла.

4. Четыре метода для решения всех предложенных задач определения сходства Г-орграфов: а) расширенный ММРЧР, Ь) метод поиска общей части структур одного Т-орграфа, с) метод поиска общей части двух графов - попарного сходства структур двух Т-орграфов, метод определения максимального общего подграфа (фрагмента) для двух полных графов с весами на ребрах.

5. Два подхода к разработке методов анализа локальных и глобальных свойств Г-орграфов и определения их сходства на основе моделей сложности Г-орграфов.

Практическая полезность

Созданные методы и разработанные на их основе программные комплексы

позволяют повысить качество и эффективность решения задач, связанных с

определением структурного сходства систем в приложениях структурной

информатики, в разработке ИПС структурной информации, в системах искусственного интеллекта с правдоподобными рассуждениями, системах поддержки принятия решений, системах структурного распознавания образов и др., а также шире использовать орграфы в теории и практике программирования, в повышении широты использования компьютерных систем при интеллектуальном анализе сложноорганизованных данных, в семантическом 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). Личный вклад диссертанта

Автор диссертации продолжает развитие методов структурного спектрального анализа для решения задач определения сходства ГМС и прошел весь путь от анализа задач определения сходства графов и ациклических орграфов до создания методологии решения задач и комплексов прикладных программ для определения сходства орграфов, темпоральных орграфов и проведения научных исследований. Наиболее существенный личный вклад автора содержится в а) разработке классификации задач определения сходства орграфов, Ь) формализованной постановке новыхх классов задач определения сходства Г-

орграфов и методов их решения, о) развитии методов надструктурной характеризации на класс орграфов с использованием в ней полупутей, d) создании методов надструктурной характеризации Г-орграфов, в) разработке и сравнительном анализе двух подходов к исследованию локальных и глобальных свойств Г-орграфов на основе моделей сложности, /) разработке методов и эффективных программных средств решения задач определения и исследования сходства орграфов и Г-орграфов. Публикации

Основные результаты, полученные в процессе выполнения диссертационной работы, опубликованы в 23 печатных трудах, из них 5 опубликованы в журналах, входящих в Перечень ВАК РФ. Структура и объём работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 132 наименования, и пяти приложений. Содержание работы по главам

Во введении обоснована актуальность темы диссертации, поставлены цели и задачи исследования, сформулированы научная новизна и практическая значимость результатов работы, кратко охарактеризовано ее содержание по главам.

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

Во второй главе дано формализованное определение £-модели для характеризации орграфов в базисе полупутей и выделены подмодели,

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

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

1 Алгоритма с полиномиальной вычислительной сложностью.

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

В четвертой главе описано расширение на класс Г-орграфов обобщенного надструктурного подхода для решения задач количественного определения сходства и кластеризации орграфов. Для характеризации глобальных свойств ^ орграфов предложена система уточняемых моделей сложности и описан метод мониторинга свойств ^орграфов по изменению значений моделей сложности. Приведены оригинальные формализованные постановки задач анализа сходства Г-орграфов, включающие 28 видов задач и предложены методы их решения с использованием Н-подхода.

В Заключении сформулированы основные результаты и выводы по работе.

В приложениях приведены: 1) обоснование справедливости утверждения 1.1; 2) алгоритм определения сходства ордеревьев; 3) экспериментальные оценки вычислительной сложности алгоритмов решения задач; 4) перечень разработанных программ, примеры областей применения методов определения сходства ГМС, описание внедрений результатов при решении задач распознавания, сравнения видеографической информации с эталоном и решении задач анализа взаимодействия акторов в корпоративной социальной сети; 5) копии актов о внедрении результатов диссертации.

1. основные подходы к определению сходства графовых моделей систем

1.1. Задачи определения сходства графовых моделей систем и подходы

к их решению

При анализе сходства ГМС важным является не только сравнение топологических характеристик структур, но и комплексный учёт класса структур, весов вершин и рёбер/дуг, ограничений на расположение и сходство расположения фрагментов и др. В первую очередь актуальной является классификация задач определения сходства с учетом особенностей классов анализируемых ГМС (см. раздел 1.3), что поможет разработать более эффективные алгоритмы анализа сходства и формировать новые виды отношений эквивалентности, толерантности и подобия. В работах [2, 12, 27, 28, 37, 40, 59, 60, 83, 101, 102, 116, 118, 121] рассматриваются четыре подхода к определению структурного сходства ГМС: 1) подструктурный подход (П-подход), 2) расширенный П-подход, 3) обобщенный П-подход на основе использования надграфов, характеризующих расположение фрагментов в ГМС, 4) структурно-характеристический подход (СХ-подход) на основе использования моделей сложности (инвариантов) ГМС.

1.1.1. Подструктурный подход и его развитие Будем говорить, что сформулирована классическая задача определения сходства орграфов, если заданы следующие параметры: . ^={GbG2,...,G„} - множество орграфов; . D(Gi,GJ) - значение расстояния между орграфами Gi и G-, . SI(Gi,Gj) - значение индекса сходства Gi, Gj.

Необходимо построить матрицу (граф) попарных расстояний между парами орграфов или матрицу коэффициентов (граф) попарного сходства.

Таким образом, задача определения сходства на множестве орграфов ^ определена, если задана тройка параметров: SIM = D, SI).

Под результатом решения задачи определения сходства набора из п орграфов будем понимать полный граф с п вершинами, каждое ребро которого ^^^ взвешено значением расстояния D(Gi (индекса сходства SI(Gi

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

Концепция П-подхода базируется на использовании максимальных общих фрагментов двух графов. Пусть Ф обозначает множество графов, определенных с точностью до изоморфизма.

Подграфовая метрика: ^ К0, где К0 - множество неотрицательных

целых чисел, определена через 0±(С,Н) =тт[1С1 + 1Н1 —21С1}, где минимум берется по всем графам C, которые являются подграфами и в графе G, и в графе Н, а G, Не Ф 2. Таким образом, величина сходства зависит от размера (числа вершин и/или ребер) максимального общего фрагмента (МСР) анализируемых графов. Меры расстояния (ф), индексы сходства ^1) и несходства (DSI) G1 и G2

-5

вычисляются по формулам :

1. Dl(Gl&2)=p(Gl)+p(G2)-2p(MCS(GlG2)).

2. D2(Gl,G2)=p(Gl)+q(Gl)+p(G2)+q(G2)-2(p(MCF(Gl,G2))+q(MCF(Gl,G2))).

3. SIl(Gl,G2)=p(MCS(Gl,G2))2/(p(Gl)p(G2)).

4. DSIl(Gl,G2)=1-SIl(Gl,G2).

. ) = (р(МСГ(С1,С2}) + д(МСГ(С1,С2)))2

. 2( 1 2) (Р(С1) + Ч(С1))(Р(С2) + Ч(С2)) .

6. DSI2(GlG2)=1-SI2(GlG2).

В П-подходе (рис. 1.1) главная проблема - проблема определения MCS или MCF, которая является ^Р-полной [23]. Выделим классический П-подход [83,

2 Willett P., Willett J. Similarity and Clustering in Chemical Information Systems. — John Wiley & Sons, 1987. — 254 p.

3 Chartrand G., Kubicki G., Schultz M. Graph similarity and distance in graphs. Aequationes Mathematicae 55. 1998. - P.129-145.

118], расширенный П-подход (РП-подход) [19] и обобщенный П-подход (ОП-подход) [35, 42]. П-подход нашел широкое применение в химической и биологической информатике при исследовании корреляций вида «структура-свойство» [122].

Рис. 1.1. Общая схема выполнения П-подхода и РП-подхода определения

сходства.

Однако, до сих пор не разработаны алгоритмы для исследования и применения возможностей П-подхода при анализе орграфов. Расширение П-подхода повышает его различительную способность, но увеличивает как временную, так и емкостную вычислительную сложность. Основная суть РП-подхода заключается в использовании информации обо всех максимальных общих фрагментах (МОФ) ГМС и учете их сложности. Результаты исследования РП-подхода при исследовании ациклических структур, состоящих из орграфов без контуров и деревьев, приведены в [19].

ОП-подход в применении к учету сходства расположения фрагментов в графах предложен в [25]. Основная его суть заключается в использовании граф-моделей ^о-моделей), позволяющих точно охарактеризовать расположение фрагментов в ГМС и на этой основе определять сходство ГМС с учетом сходства расположения фрагментов. На рис. 1.2 приведены примеры gs- и gsо-моделей, характеризующих сходство расположения подграфов Cз и C4, и орбитами подграфов в графе G. ОП-подход выполняется в два этапа. Сначала определяется сходство расположения фрагментов, которые интересуют исследователя, а затем

сходство ГМС с учетом сходства расположения фрагментов на основе определения МОФ построенных ££о-моделей (рис. 1.3). Результаты программной реализации ОП-подхода для обыкновенных графов и исследования эффективности его применения приведены в [41, 44, 45, 61]. Главная отличительная особенность ОП-подхода состоит в том, что он позволяет решать новый класс задач - задач определения сходства расположения фрагментов при точной характеризации их расположения.

Расширение возможностей применения ОП-подхода, связанное с учетом информации о сходстве расположения полупутей при точной характеризации их расположения в ордеревъях общего вида, предложено автором в [50]. Ниже под ордеревом общего вида понимаем связный орграф, в котором между каждой парой вершин существует только один простой полупуть.

Анализируемый граф О

Сз

С4

Модель сходства расположения _подграфов С3 и С4_

Модель сходства расположения орбит _подграфов С3 и С4_

^(С) = [шшС|-4ш П]

^о(С) = [шшС|_4^п П0]

Рис. 1.2. Примеры моделей, характеризующих сходство расположения подграфов и орбит подграфов С3 и С4 в графе О.

К достоинствам ОП-подхода на основе £.ад-моделей можно отнести его универсальный общесистемный характер анализа сходства ГМС с учётом точного расположения произвольных фрагментов и многообразие их подмоделей с различными свойствами. Недостаток подхода - сложность настройки на

Список литературы диссертационного исследования кандидат наук Кохов Виктор Викторович, 2016 год

список литературы

1. Айзерман М.А., Гусев Л.А., Петров С.В., Смирнова И.М. Динамический подход к анализу структур, описываемых графами (основы графодинамики) // АиТ. 1977. №7. - С. 116-150

2. Аксёненков Ф. В., Кохов В. А., Мельников Н. И. и др. Интеллектуальная система для анализа данных о метаболизме // Труды II Международной конференции «Системный анализ и информационные технологии» (САИТ-2007), Россия. Москва, Т.2, 2008. - С. 101-104.

3. Артамонов Г.Т. Топология регулярных вычислительных сетей и сред. М. 1985.

4. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и микропроцессорных сетей. М. Радио и связь, 1986.

5. Берштейн Л.С., Боженюк А.В. Использование темпоральных графов как моделей сложных систем // Известия ЮФУ. Технические науки. 2010. №4 (105). - С. 198-20

6. Берштейн Л.С., Мелехин В.Б. Нечеткие динамические семантические сети для представления знаний интеллектуальных систем управления//Автоматика и телемеханика. 2000, вып. 3. - С. 123-129.

7. Воронцов К. В. Локальные базисы в алгебраическом подходе к проблеме распознавания. Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН, 1999. - 122 с.

8. Градосельская Г. Роль неформальных взаимодействий в организации бизнес-структур: сетевой подход. 2011.

9. Грибков И.В., Захаров А.В., Кольцов П.П. и др. Сравнительное исследование методов анализа изображений. М. НИИСИ РАН. 2005. - 156 с.

10. Грызунов А.Б., Кохов В.А. Метод сокращения перебора на основе учета симметрии при решении NP-полных задач на графах //МЭИ. М, 1987. - 58 с. деп. ВИНИТИ, 18.08.87, №6029-В87.

11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., Мир, 1982.

12. Джасим М. Р. Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур. Дис. ... канд. техн. наук. М: МЭИ, 2010.

13. Домахина Л. Г. Скелетная сегментация и циркулярная морфология многоугольников. Диссертация к.ф.-м.н. М. 2013. 149 с.

14. Журавлев Ю. И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз, Т. 1, 1988.

15. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, Т. 11, 1978. - С. 5-68.

16. Загоруйко Н.Г., Скоробогатов В.А., Хворостов П.В. Вопросы анализа и распознавания молекулярных структур на основе общих фрагментов //Алгоритмы анализа структурной информации. - Новосибирск. 1984. Вычислительные системы. Вып. 103. - С. 26-50.

17. Задонский Д., Макарова Е., Мехедов И. Топологическая модель многоуровневой улично-дорожной сети на основе скелета. - С. 1-8. http://www.graphicon.ru/html/2010/conference/RU/Se4/110.pdf

18. Затуливетер Ю-C., Фищенко Е.А. Графодинамические системы с сетецентрическим управлением в математически однородном поле компьютерной информации // Управление большими системами: сборник трудов: Сетевые модели в управлении. ИПУ РАН. 2010. № 30-1. С. 567-604.

19. Ибрахим А. Р. Разработка методов и пограммных средств для анализа сходства ациклических структур. Диссертация на соискание ученой степени к.т.н. М. МЭИ. 2009. - 155 с.

20. Карпухин И.Н., Яркин С.В., Кохов В.А. Генераторы средних по сложности структур для исследования базовых алгоритмов структурной информатики. Труды 13 международной научно-технической конференции «Радиоэлектроника, электротехника и энергетика», Т1. М., МЭИ, 2007. - С. 364-365.

21. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 200 - 1104 с.

22. Клещев А.С., Шалфеева Е.А. Определение структурных свойств онтологий // Изв. РАН. Теория и системы управления. 2008. №2. - С. 69-78.

23. Климентовский А.Н. Метод построения моделей сложности для семантических сетей. Магистерская диссертация. М. НИУ ВШЭ. 2010.

24. Кольцова П.П. Разработка методологии сравнительного исследования компьютерных методов обработки изображений. Автореферат диссертации на соискание ученой степени д.т.н. НИИСИ РАН. 2012.

25. Кохов В.А. Граф-модели для определения сходства структур систем с учетом сходства расположения фрагментов. Десятая Национальная конференция по искусственному интеллекту с международным участием. КИИ-2006: Труды конференции. В 1-х т. Том М.: Физматлит, 2006. - С. 208216.

26. Кохов В.А. Граф-модели для анализа сходства структур на основе их сложности. Одиннадцатая национальная конференция по искусственному интеллекту с международным участием. КИИ-2008: Труды конференции. В 1-х т. Том 2. М.: ЛЕНАНД, 2008. - С. 70-78.

27. Кохов В.А. Концептуальные и математические модели сложности графов. -М: Изд-во МЭИ, 2002. - 190 с.

28. Кохов В.А. Модели и методы анализа сходства графов для поиска структурной информации // Труды международной конференции «Информационные средства и технологии», МФИ-2005, Том 2. М., МЭИ, 2005. - С.79-82.

29. Кохов В.А. Модели и методы анализа сходства графов для поиска структурной информации // Труды международной конференции «Информационные средства и технологии». (МФИ-2005), Т.2, Москва, 2005. - С. 79-82.

30. Кохов В.А. Основы структурной информатики // Труды международной конференции «Информационные средства и технологии». (МФИ-98), Москва, 1998. - С. 48-53.

31. Кохов В.А. Структурная информатика: содержание и проблемы. Труды международной конференции. МФИ-2001,Т Москва, СТАНКИН, 2001 -С.42-45.

32. Кохов В.А., Горшков С.А., Ибрахим А. Р, Джасим М.Р. АСНИ «Мастерская граф-моделей»: подсистема структурного спектрального анализа деревьев. Труды международной конференции «Информационные средства и технологии», МФИ-2006, Т2. Москва, МЭИ, 2006. - С. 104-108.

33. Кохов В.А., Джасим М.Р., Кохов В.В. Интегрированная среда визуального и алгоритмического решения задач поиска, сравнительного анализа и определения сложности ациклических графовых моделей систем. // ПСУН по дисциплинам «Структурный анализ систем», «Теория графов и комбинаторика», «Дискретная математика», «Построение и анализ эффективных алгоритмов» и др. / Паспорт от 18.06.2009 г. - М., МЭИ, 2009.

34. Кохов В.А., Ибрахим А.Р., Кохов В.В. Интегрированная среда визуального и алгоритмического решения задач поиска и анализа сходства ациклических графовых моделей систем. // ПСУН по дисциплинам «Структурный анализ систем», «Теория графов и комбинаторика», «Дискретная математика», «Построение и анализ эффективных алгоритмов» и др. / Паспорт от 18.06.2009 г. - М., МЭИ, 2009.

35. Кохов В.А., Кохов В.В. Граф-модели для анализа сходства структур систем на основе обобщенного подструктурного подхода // Тр. XII национальной конф. по искусственному интеллекту с международным участием. КИИ-2010, Том Физматлит. М., 2010. - С.111-14

36. Кохов В.А., Кохов В.В. Методы анализа изменений глобальных и локальных свойств темпоральных орграфов. Бизнес-информатика. 2012. №03. С. 42-51.

37. Кохов В.А., Кохов В.В. Модели и методы анализа сходства сетей на основе их сложности. Труды десятой международная научно-практическая конференция (ПФИС-2008). Новосибирск, 2008. - С. 251-258.

38. Кохов В.А., Кохов В.В., Джасим М.Р. Модели для анализа структурной сложности систем // Вестник МЭИ, №1, 2010. - С.1-14.

39. Кохов В.А., Кохов В.В., Ибрахим А.Р. Система моделей для анализа сходства графов с учетом расположения цепей // Вестник МЭИ, №5, 2009. -С. 5-13.

40. Кохов В.А., Незнанов А.А., Ткаченко С.В. Задачи анализа структурного сходства и методы их решения // Труды XII Национальной конференция по искусственному интеллекту с международным участием. КИИ-2010 т. Том М.: Физматлит, 2010. - С. 161-169.

41. Кохов В.А. Задачи и методы определения сходства темпоральных орграфов // Современная наука: актуальные проблемы теории и практики. Серия: естественные и технические науки, №2, 2016. - С. 44-51.

42. Кохов В.А., Незнанов А.А., Ткаченко С.В. Компьютерные методы анализа сходства графов. Девятая Национальной конференция по искусственному интеллекту с международным участием. КИИ-2004: Труды конференции. В 1-х т. Том М.: Физматлит, 2004. - С. 162-170.

43. Кохов В.А., Незнанов А.А., Ткаченко С.В. Новые программные средства для поиска структурной информации // Труды международной научно-технической конференции «Информационные средства и технологии». (МФИ-2005), Т.2, Москва, 2005. - С. 81-86.

44. Кохов В.А., Незнанов А.А., Ткаченко С.В. Программные средства для исследования сложности и сходства графовых моделей систем. // Труды ИВМиМГ, Информатика, 7, (Материалы Третьей азиатской международной школы-семинара «Проблемы оптимизации сложных систем»), Новосибирск, 2007. - С. 268-27

45. Кохов В.А., Незнанов А.А., Ткаченко С.В. Программный комплекс для формирования и исследования отношений эквивалентности и толерантности на структурах. Десятая Национальная конференция по искусственному интеллекту с международным участием. КИИ-2006: Труды конференции. В 1-х т. Том М.: Физматлит, 2006. - С. 199-207.

46. Кохов В.А., Незнанов А.А., Ткаченко С.В. Структурная информатика -новый актуальный раздел информатики для изучения в школе и университете. 1 -ое Всероссийское совещание НМС по информатике «Актуальные проблемы информатики в современном российском образовании»: Труды / Отв. ред. Ю.И. Журавлев, В.В. Тихомиров. - М.: МАКС ПРЕСС, 2004 . - С. 250-276.

47. Кохов В.А., Ткаченко С.В. Исследование алгоритмов структурной информатики с помощью ППП «ПОЛИГОН-СТРИН». М.: Издательство МЭИ, 2005. - 68 с.

48. Кохов В.А., Ткаченко С.В. Решатель базовых задач структурной информатики. М.: Издательство МЭИ, 2006. - 192 с.

49. Кохов В.В. Задачи и методы анализа сходства темпоральных орграфов. Труды 14-ой национальной конференции по искусственному интеллекту с международным участием. КИИ-2014. Том 3. Казань: Изд-во РИЦ "Школа". 2014. - С. 155-163.

50. Кохов В.В. Методы определения сходства ордеревьев на основе обобщенного подструктурно-метрического подхода // Актуальные проблемы гуманитарных и естественных наук. 2012. №05 (40). - С. 68-72.

51. Кохов В.В., Фальк В.Н. Структурная информатика: система моделей для анализа сходства орграфов. Труды 16 международной НТК «Радиоэлектроника, электротехника и энергетика», Т1. М., Издательский дом МЭИ, 2010. - С. 363-364.

52. Кохов В.В., Фальк В.Н. Структурная информатика: трансграфы деревьев, ордеревьев и их свойства. Труды 17 международной НТК «Радиоэлектроника, электротехника и энергетика», Т1. М., Издательский дом МЭИ, 2012. - С. 372-373.

53. Кохов В.В., Фальк В.Н. Структурная информатика: трансграфы полупутей для ордеревьев и их свойства. Труды 18 международной НТК «Радиоэлектроника, электротехника и энергетика», Т1. М., Издательский дом МЭИ, 2012. - С. 372-373.

54. Кузнецов С.О., Финн В.К. Распространение процедур ЭС типа ДСМ на графы // Техническая кибернетика, 1988, №5, С.4-11.

55. Курейчик В.М. Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990.

56. Курейчик В.М., Каляев А.В, Мелихов А.Н., Гузик В.Ф., Калашников В.А. Автоматизация проектирования вычислительных структур. Монография. Изд-во Ростовского ун-та, 1983.

57. Курейчик В.М., Родзин С.И. Контролепригодное проектирование и самотестирование СБИС: проблемы и перспективы. М.: Радио и связь, 1994.

58. Лаптырев Д.А. Система управления финансовыми ресурсами банка: Процессы - задачи - модели - методы. БДЦ-пресс. 2005.

59. Лебедев К.С., Кохов В.А., Шарапова О.Р. и др. Опознание крупных структурных фрагментов неизвестного соединения с помощью поисковой системы по ИК-спектрам // Сибирский химический журнал. 199 Вып. - С. 50-56.

60. Москин Н.Д. Теоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация: Дис. ... канд. техн. наук. Петрозаводск: Петрозаводский государственный ун-т, 2006.

61. Незнанов А.А., Кохов В.А. Программный комплекс структурного сходства систем с учетом расположения фрагментов // Программные продукты и системы, № 4, 2010. - С. 147-150.

62. Нечепуренко М.И., Попков В.К., Кохов В.А. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука, 1990. - 515 с.

63. Применение теории графов в химии /Ред. Зефиров Н.С., Кучанов С.И., Наука. 1988. 306 с.

64. Раппопорт А.М. Измерение расстояния между взвешенными графами экспертных суждений.

65. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М. Наука. 1986. 496 с.

66. Скороходько Э.Ф. Семантические сети и автоматическая обработка текста / Э.Ф. Скороходько. - Киев: Наукова думка, 1983. - 217 с.

67. Соколовский В.В. Исследование качества автоматической классификации текстовых документов с использованием семантического графа документа: Труды. XII Междунар. конф. «Библиотеки и информационные ресурсы в современном мире науки, культуры, образования и бизнеса». Крым-2005. М.: ГПНТБ России, 2005.

68. Финн В.К. ДСМ-метод автоматического порождения гипотез. Логические и эпистемологические основания. Либроком. 2009. 432 с.

69. Финн В.К. Об интеллектуальном анализе данных // Новости Искусственного интеллекта, №3. 2004.

70. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ. Итоги науки и техники. Информатика, Т.15, М.: 1991, с. 54-101.

71. Химические приложения топологии и теории графов. Пер с англ. /Под ред. Р Кинга. - М.: Мир, 1987. - С.259-265.

72. Химические приложения топологии теории графов / Ред. Р. Кинг, М.: Мир. -1987. С. 222-235.

73. Штанчаев Х.Б. Применение графовой модели и априорного классификатора для сегментации изображения в задачах распознавания лица человека // Интернет - журнал «НАУКОВЕДЕНИЕ». Том 7, No2. 2015. - С. 1-15.

74. Advances in Mining Graphs, Trees and Sequences. Ed. Washio T., Koka J.N.,De Raedt L. 2005. - 220p.

75. Alexey A. Neznanov, Victor A. Kokhov, Sergey V. Tkachenko. New mathematical models and software tools for complexity and similarity analysis of molecular graphs // Fourth International Symposium Computational Methods in Toxicology and Pharmacology Integrating Internet Resources (CMTPI-2007), Abstract Book, Moscow, 2007. - P. 127.

76. Bai X., Latecki L.J. Path Similarity Skeleton Graph Matching. http://mc.eistar.net/mclabwebold/Paper/PAMIshape07.pdf

77. Basu P., Bar-Noy A., Ramanathan R., Johnson M. Modeling and Analysis of Time-Varying Graphs. 2010. ArXiv: 1012.0260.

78. Bhele S. G., Mankar V. H. A Review Paper on Face Recognition Techniques// International Journal of Advanced Research in Computer Engineering & Technology (IJARCET) V. 1, Issue 8, October 2012. - P. 339-346.

79. Blondel V. D., Gajardo A., Heymans M., Snellart P., Van Dooren P. A measure of similarity between graph vertices: applications to synonym extraction and web searching, SIAM Review 46. 2004. - P. 647-666.

80. Braha D., Bar-Yam Y. Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interaction // Adaptive Networks: Theory, Models and Applications / ed. by T. Gross, H. Sayama. Springer, Dordrecht, 2008. P. 39-50.

81. Bramsen P.J. Doing Time: Inducing Temporal Graphs. Technical report, Massachusetts Institute of Technologi. 2006. 51 p.

82. Brennecke A., Isenberg T. 3D Shape Matching Using Skeleton Graphs

83. Bunke H. and Shearer K. A graph distance metric based on maximal common subgraph. Pattern Recognition Letters, Vol. 19, N. 1-4, 1998. - P.255-259.

84. Bunke H. Graph Matching: Theoretical Foundations, Algorithms, and Applications. - P. 1-7. http://www.ai.rug.nl/ki2/literature/graphmatch-bunke.pdf

85. Chartrand, G., Kubicki, G., Schultz, M.: Graph similarity and distance in graphs. Aequationes Mathematicae 55. 1998. - P.129-145.

86. Choe T.E., Deng H., Guo F., Lee M.W., Haering N. Semantic Video-to-Video Search using Sub-Graph Grouping and Matching. ICCV2013.

87. Dickinson S., Pelillo M., Zabih R. Special section on graph algorithms in computer vision, IEETrans. Patt. Anal. Mach. Intell. 23. - 2001. - Р. 1049-1052.

88. Eckmann J.P.,Moses E.,Sergi D. Entropy of dialogues creates coherent structure sineail traffic. Proc. Natl. Acad. Sci.USA101. 2004. - P. 14333-14337.

89. First International Workshop on Mining Graphs, Trees and Sequences (MGTS-2001).

90. Fortunato S. Community Detection in Graphs // Physics Reports. 2010. № 486. -P. 75-174.

91. Ghoshal G., Barabasi A.-L. Ranking Stability and Super-Stable Nodes in Complex Networks //Nature Communications. 2011. № 2. P. 1-7.

92. Hanan ElNaghy H., Hamad S., Khalifa M.E. Taxonomy for 3d content-based object retrieval methods /IJRRAS14 (2) February 2013. - P. 412-446.

93. Hau J., William Lee W., Darlington J. Semantic Similarity Measure for Semantic Web Services. 2005. http://www.ra.ethz.ch/cdstore/www2005-ws/ workshop/ wf0 8/wss2005-hau- fi nal. pdf

94. Heymans M., Singh A. Deriving phylogenetic trees from the similarity analysis of metabolic pathways//Bioinformatics 19. 2003. - P. 138-146.

95. Holme P., Saramaki J. Temporal Networks. 2011. ArXiv: 1108.1780 v1.

96. Jackson M.O. Social and Economic Networks. Princeton University Press, 2008. 647 p.

97. Jeh G., Widom J. SimRank: A Measure of Structural-Context Similarity. Stanford University. - P. 1-11.

98. Jiang W., Xu K., ChengZ.Q., Martin R.R., Dang G. Curve skeleton extraction by coupled graph contraction and surface clustering / Graphical models. 75 (2013). -P. 137-148.

99. Johanson M. A. A Review and Examination of the Mathematical Spaces Under lying Molecular Similarity Analysis. //Journal of Math. Chem., 1989, vol. 3. no. 2, - P. 117-146.

100. Klenk S., Dippon J., Fritz P., Heidemann G. Determining Patient Similarity in Medical Social Networks. MEDEX 2010. Proceedings. - P. 6-13.

101. Kokhov V.A. Methods, Algorithms and Programs for Analysis of Molecular Graph Similarity // The Fourth Japan-USSR Simposium on Computer Chemistry. October 28-10, 199 Toyohashi University of Technology, Japan. 199. - P. 51-54.

102. Kokhov V.A. Two Approaches to Determining Similarity of Two Digraphs // Journal of Computer and Systems Sciences International, 2012, Vol. 51. - P. 695714.

103. Kostakos V. Temporal Graphs //Physica A. 2009. № 388. - P. 1007-1023.

104. Kubicka E., Kubicki G., Valdis I. Using Graph Distance in Object Recognition.

105. Kuhn F., Oshman R. Dynamic Networks: Models and Algorithms // ACMSIGACT News. 2011. № 42. - P. 82-96.

106. Kuwata Y. Decomposition Algorithm for Global Reachability Analysis on a Time-Varying Graph with an Application to Planetary Exploration // Inter-national Conference on Intelligent Robots and Systems. 2009.

107. Lee J.K., Oh J.,H., Hwang S. Clustering of video objects by graph matching.

108. Leicht E. A., Holme P., Newman M. E. J. Vertex similarity in networks, Physical Review E 73. 2006. 026120.

109. Lu S., Lyu M.,R., King I. Video Summarization by Spatial-Temporal Graph Optimization, Proceedings of the 2004 International Symposium on Circuits and Systems, Vancouver, Canada, May 2004. vol. 2. - P. 197-200.

110. M. Rundic, C.L. Wilkins. Graph Theoretical Approach to Recognition of Structure Similarity in Molecules. //J. Inf. Comput. Sci. - vol. 19, no. 1. P. 16-39, 1979.

111. Marcialis G.L., Roli F., Serrau A. Graph Based and Structural Methods for Fingerprint Classification, Springer verlag, Berlin Heidelberg. 2007.

112. Mekenyan O., Bonchev D. Topological indices for molecular fragments and new graph invariants //J. Math. Chem., 1988. №.3. - P. 347-375.

113. MLG 2011 Workshop - Sun, Aug 11, Chicago, Illinois. 201.

114. Newman M. Networks: an introduction. Oxford University Press, 2010.

115. Pan R., Saramaki J. Path Lengths, Correlations, and Centrality in Temporal Networks. 2011. ArXiv: 1101.5913.

116. Pelillo M., Siddiqi K., Zucker S.W. Matching hierarchical structures using association graphs. IEEE Trans. Pattern. Anal. Mach. Intell., 21, 1999. -P. 11051120.

117. Phukon K. K. Maximum Common Subgraph and Median Graph Computation from Graph Representations of Web Documents Using Backtracking Search/ In ternational Journal of Advanced Science and Technology. Vol. 51 February, 2013.

- P. 67-80.

118. Raymond J. W., Gardiner E. J., Wllett P. RASCAL: Calculation of graph similarity using maximum common edge subgraphs //Computer Journal, vol. 45, N.6, 2002. - P. 611-644.

119. Santoro N. et al. Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics. 2011. ArXiv: 1102.0629.

120. Schenker A., Bunke H., Last M., Kandel A. Graph Theoretic Techniques for Web Content Mining, Series in Machine Perception and Artificial Intelligence, vol. 62.

121. Shearer K., Bunke H., Venkatesh S. Videoindexing and similarity retrieval by largest common subgraph detection using decision trees. Pattern Recog. 14, 200.

- P. 1075-1091.

122. Shirinivas S.G., Vetrivel S., Elango N.,M. Applications of graph theory in computer science an overview / International Journal of Engineering Science and Technology Vol. 2(9), 2010. - P. 4610-4621.

123. Skorobogatov V.A., Dobrynin A.A. Metric analysis of graphs // Comm. Math. Chem. (MATCH). 1988. №. 23. - P. 105-151.

124. Tan X., Chen S., Zhou Z., Zhang F. Face recognition from a single image per person: A survey. Pattern Recognition., 39(9). 2006. - P.1725-1745.

125. Tang J. Small-World in Time-Varying Graphs //Phys. Rev. E. 2010. № 81.

126. Tang J., Musolesi M., Mascolo C., Latora V. Temporal Distance Metrics for Social Network Analysis // Proceedings of the 2nd ACM SIGCOMM Work-shop on Online Social Networks. 2009.

127. Veksler O. Efficient graph-based energy minimization methods in computer vision. PhD thesis. Cornell University. July. 1999.

128. Vragovic I., Louis E., Diaz-Guilera A. Efficiency of informational transfer in regular and complex networks. Phys. Rev. E 71. 036122 (2005)

129. Wang Y., Ishii N. A Metod of Similarity Metrics for Structured Representation. Expert System with Applications. Vol. 12, no. 1, 1997. - P. 89-100.

130. Willett P., Willett J. Similarity and Clustering in Chemical Information Systems. — John Wiley & Sons, 1987.

131. X. Yan X, Yu P.S., Han J. Substructure Similarity Search in Graph Databases. SIGMOD. June 2005. vol.2, no. 4, 2006. - P. 259-362.

132. Zager L. Graph Similarity and Matching. MTI, 2005. - 88 p.

приложение 1. обоснование справедливости утверждения 1.1

На рис. П1.1 приведены примеры MCS трех видов связности.

Пары слабых орграфов

МСБ (слабый)

МСБ (односторонний)

МСБ (сильный)

Пары односторонних орграфов

МСБ (слабый)

МСБ (односторонний)

МСБ (сильный)

Пары сильных орграфов

МСБ (слабый)

МСБ (односторонний)

МСБ (сильный)

Пары слабый-односторонний

МСБ (слабый)

МСБ (односторонний)

МСБ (сильный)

Пары слабый-сильный

МСБ (слабый)

МСБ (односторонний)

МСБ (сильный)

Пары односторонний-сильный

МСБ (слабый)

МСБ (односторонний)

МСБ (сильный)

Рис. П1.1. Примеры MCS для всех видов пар орграфов по связности.

приложение 2. алгоритм определения сходства ордеревьев и обоснование полиномиальности алгоритма_

int FullIntersecOriented(DITREE T, DITREE S) //МИП ордеревьев T и S Входные параметры: T, S - ордеревья Выходные параметры:

Нет

Переменные:

m - промежуточный результат Возвращаемое значение:

Размер МИП ордеревьев T и S

1 m=0;

2 for (i е V(T))

3 for (int j = 0; j < S.Count; j++) {

4 l = IntersecBranchOriented(T, S, i, j, 0, 0); }

5 if (l > m) m = l;

6return m;

int IntersecBranchOriented(DITREE T, DITREE S, int downT, int downS, int upT, int upS)

// Пересечение корневых ордеревьев от вершин downT и downS ордеревьев T и S соответственно

Входные параметры:

T, S - ордеревья, downT и downS - вершины сответсвующие корню, upT и upS -вершины лежащие выше корня (если имеются) Выходные параметры:

Нет

Переменные:

Matr - матрица попарного пресечения корневых ордеревьев Res - соответствия для максимального паросочетания

Summa - стоимость взвешенного паросочетания (сумма весов ребер в пересечении) Возвращаемое значение:

Размер МИП корневых ордеревьев от вершин downT и downS ордеревьев T и S соответсвенно

1 for (i е T(T, downT) //сопоставляем вершины i и j и ищем максимальную общую ветвь, идём по всем, с которыми связана вершина i

2 if (i != upT && i != 0) //если не пришли "назад" или совсем в начало (upT -откуда пришли, 0 - значит, что это первая вершина в рассмотрении

3 for (j е Г(S, downS)) {

4 if (j != upT && j != 0) //как и с i {

5 if (T[downT][i].Or == S[downS][j].Or) //проверяем ориентацию

{

6 Matr[T[downT][i].X, S[downS][j].X] = IntersecBranchOriented(T, S,

T[downT][i].X, S[downS][j].X, downT, downS); }

}

}

7 res = KuhnMunkres(Matr); //ищем максимальное паросочетание

8 for (int k = 0; k < res.Count(); k++)

{

summa += Matr[k, res[k]];

}

9 return summa + 1; //здесь +1, т.к. учитывается вес вершины

Ниже приведено доказательство полиномиальной вычислительной сложности алгоритма МИП пары ордеревьев от числа вершин исходных ордеревьев. Будем предполагать, что max(V(T), V(S)) = n. Утверждение П2.1.

Функция IntersecBranchOriented, использованная в виде IntersecBranchOriented(T, S, u, v, 0, 0), где u и v любые вершины ордеревьев T и S соответственно, будет рекурсивно вызвана не более чем V(T)V(S) раз. Доказательство.

Для любых пар вершин p и q ордеревьев T и S соответственно, в ходе выполнения функции IntersecBranchOriented(T, S, u, v, 0, 0) функция IntersecBranchOriented может быть вызвана рекурсивно с параметрами downT = p и downS = q только один раз, так как в ордереве существует только один полупуть между двумя любыми вершинами. Поэтому попасть в рекурсивную ветвь IntersecBranchOriented с параметрами downT = p и downS = q можно только одним полупутем из вершин p и q. Следовательно, максимально возможно число раз, которое будет вызвана рекурсивно функция IntersecBranchOriented, составляет количество возможных пар вершин ордеревьев - V(T)V(S) Следствие П2.1.

Вычислительная сложность функции IntersecBranchOriented от числа вершин n исходных ордеревьев:

Л

/Мш_кд(п) = n(n)-O(n ), где П(п) - вычислительная сложность функции KuhnMunkres. Максимальный размер матрицы для поиска максимального взвешенного паросочетания не превосходит максимальную степень вершин ордеревь-ев, которая в свою очередь не превосходит n.

Вычислительна сложности алгоритма поиска максимального взвешенного

-5

паросочетания KuhnMunkres : П(п) =O(n ), где n - порядок матрицы.

Следствие П2.2.

Вычислительная сложность функции FullIntersecOriented от числа вершин n исходных ордеревьев:

2 4 7

/мип_д (n) = O(n ) X/мипкд(п) = n(n)-O(n ) = O(n ).

Приведенные выше обоснования ставят целью лишь обосновать полиномиальный характер вычислительной сложности алгоритма.

приложение 3. экспериментальные оценки вычислительной сложности алгоритмов решения задач

П3.1. Задача построения НПП для планарных ОГ высокой сложности

Время работы алгоритма построения cgph-модели прямо пропорционально количеству добавляемых в граф-модель вершин-полупутей и поэтому в общем случае экспоненциально возрастает с увеличением длин путей, анализируемых орграфов. На рис. П3.1-2 приведены ЭОВС алгоритма построения ghp для базиса с длиной 5 и 19. Число вершин в НПП растет как полином степени 2: y2=8x2+42x+41 ^2=1); y4=135x2+336x+203 (ДМ).

с о о

5 о о 5

С о

П X 4

X

К л 3

с! -

К 2

:>

е -

р 1

т

у = 8405,8х2 - 46091х + 61255 R2 = 0,9936

10 14 18 22 26 30 34 38 42 46 50 Число вершин ПОГ

с 5 .о х о 20

С е;

П е; 15

X 1

к

л с! 10

К

? 5

е

р

т

0

у = 543,32х5 + 2197х4 54829х3 + 74608х2 + 2752,5х + 53253 R2 = 1

14 18 22 26 Число вершин ПОГ

Рис. П3.1.

Рис. П3.2.

П3.2. Задача построения НПП для случайных ОГ плотности 8%

На рис. П3.3 приведены ЭОВС алгоритма построения ghp методом достройки вершины до полупути максимальной длины и далее достройки по всем подграфам этого полупути для базиса полупутей с длиной 5 и 19. Число вершин в НПП растет как полином степени 2:

к с; Ч к

(и а со

35 30 25 20 15 10 5 0

4

у = -5635,2х5 + 118165х4 У

884281х3 + 3Е+06х2 - у

4Е+06х+2Е+06

R2 = 0,9975 /

У

♦ » » —

10 14 18 22 26 30 34 38 Число вершин орграфа

Рис. П3.3.

Рис. П3.4.

6

0

П3.3. Задача определения сходства орграфов на основе вектор-индекса сложности в базисе полупутей

На рис. П3.5 приведены графики времени определения сходства двух ОГ для следующих длин базиса полупутей: 5 (А), 9 (В), 35 (С). Анализировались случайные орграфы с плотностью заполнения матрицы смежности 8% и числом вершин от 20 до 120.

о о

° о

о 3

1-4

X

и 2

(и

СР

со

0007 Л л^3 J

у -170 337,4 99х2 +8Х4 - - 287' 398 7 18х + ,1Х3 + 1549 Г Т/

R 2 = 0, 9966

20

40 60 80 100 число вершин

120

40

о о о

3 30

X

У 20 | 10

е р0

СО

1042 ,х4 - 7 ,х - 7 695 695 3

у = 24 497х 2 - /

4 31625 П2 х + 1 — ПС 3583 оо > зд

R2 - 0,9 99,/

20

40 60 80 100 120 число вершин

А

В

80

0 0 00060 0

«9

40 20

у = 27806х4 - 24386х3 + 81639х2 -_- 1Е+06х + 53563

R2 = 1

(и

СР

со

20 40 60 80 100 120 число вершин

С

Рис. П3.5.

Анализ графиков приводит к выводу о достаточной эффективности для практического применения алгоритма при анализе орграфов до 400 вершин и ограничении на длину базиса до 35 фрагментов включительно.

П3.4. Задача построения Ь-моделей в разных по длине базисах

На рис. П3.6-9 приведены ЭОВС алгоритма построения ¿-моделей вида Vе <^ИР методом достроек на основе обхода ОГ в глубину соответственно для ордеревьев средней сложности (базис длины 35), для случайных орграфов плотности 3% (базисы длин 5, 9 и 19).

550

500

450

400

с 5 350

300

ОС 5 250

е 200 -

р т 150

100

Л Г\ Л Л С.. . Г ~7 Г* Г*-7

у - 49,1 15Х + 5 7 ,66 7^^

Р2 - 0,9974 ^

38 68 98 128158188218248278308 Число вершин ордерева

у = 6079,5х3 - 38854х2 + 82821х - 51455

35 8 30 8 25

X 20

о 15

2 10 * 5

5 0

0) £1 т

Рис. П3.6.

Рис. П3.7.

0

о

к 2

10 9 8 7 6 5 4 3 2 1

£ о

Ш

у = 56,003х3 - 470,43х2

+ 1512,9х - 1157,6

R2 = 0,9925

Число вершин_дуг

Рис. П3.8.

10

о о

2 4

К 2

£ 0 ш

у = 3274,2х2 - 15939х

+16821 R2 = 0,9907

V/ > V V» Ч -о

* ' о*'

А'

Число вершин и дуг

Рис. П3.9.

6

приложение 4. разработанные программные комплексы и их применение

П4.1. Основные программы, входящие в разработанные комплексы программ

Созданы два программных комплекса: «Сходство орграфов» и «Сходство темпоральных орграфов». Программы разработаны на языках C# и C++ в среде Microsoft Visual Studio 2010. Программные комплексы имеют две версии: 1) расширение функционального наполнения АСНИ «Мастерская граф-моделей» [6]; 2) библиотека методов с файловым вводом-выводом орграфов. В табл. 4.1-4.2 приведен перечень основных программ разработанных комплексов.

Таблица П4.1.

Разработанные программы комплекса «Сходство орграфов»

№ Название алгоритма Входные данные Выходные данные Вычислит. Сложность Ограничение на число вершин р

1 Построение цветного НПП для орграфа Орграф в FO Цветной НПП в FO Экспон. Р < 200

2 Построение цветного НПП для ордерева Ордерево в FO Цветной НПП ордерева в FO Экспон. Р < 6000 на ордеревьях средней сложности

3 Свертка НПП до исходного ОГ Орграф в FO Исходный ОГ в FO Полином. Р< 32000

4 Определение MCS, D\, SIl для двух рдеревьев Орграф в FO MCS, число вершин и дуг в MCS, D1, SIl Полином. Р < 6000 на ордеревьях средней сложности

5 Определение MCS для двух ОГ Орграф в FO MCS, число вершин и дуг в MCS, D1, SI1 Экспон. Р < 120 на ОГ средней сложности

6 Определение MCF для двух ОГ Орграф в FO MCF, число вершин и дуг в MCF, D2, SI2 Экспон. Р < 90 на ОГ средней сложности

7 Построение 6-модели вида [V Я? НР'ш\ для ОГ и полупутей-фрагментов Орграф в FO Матрица достроек вершин до HPw Экспон. Р < 5000 на ОГ средней сложности и полупутях длины 2

8 Пересечение 6-моделей вида [V Ше HPw\ Матрицы 6-моделей Значение D2, SI2 Полином. Р < 5000 на ОГ средней сложности и полупутях длины 2

9 Построение матрицы вкладов вершин в НР^ш для ОГ Орграф в FO Матрица вкладов вершин в базисе НР'ш Экспон. Р < 5000 на ОГ средней сложности и полупутях длины 2

10 Вычисление вектор-индексов сложности в базисе полупутей ОГ Орграф в FO Значения индексов и вектор-индексов Экспон. Р<5000 на ОГ средней сложности и полупутях длины 2

Таблица П4.2.

Разработанные программы комплекса «Сходство темпоральных орграфов»

№ Название алгоритма Входные данные Выходные данные Вычислит. Сложность Ограничение на число вершин р

1 Построение цветных НПП для каждого tОеТО Набор орграфов в ЕО Цветные НПП для каждого tGеTG в базе структур Экспон. р < 200

2 Построение цветных НПП для каждого ордерева 1С<аТО Набор ордеревьев в ЕО Цветные НПП для каждого tGеTG в базе структур Экспон. р < 6000 на ордеревьях средней сложности

3 Определение МСБ, А, Б11 для ордерева tiG1 е TG1 и ордерева tjG2еTG2 Два набора ордеревьев в ЕО MCS, число вершин и дуг в MCS, А, SI1 Полином. р < 6000 на ордеревьях средней сложности

4 Определение МСБ, А, Б11 для ОГ tiG1 е TG1 и ОГ tiG2еTG2 Два набора ОГ в ¥О MCS, число вершин и дуг в MCS, Д, SIl Экспон. р < 120 на ОГ средней сложности

5 Определение МС¥, А, SI2 для ОГ ^1 е TG1 и ОГ tiG2еTG2 Два набора ОГ в ¥О MCЕ, число вершин и дуг в MCЕ, А, SI2 Экспон. р < 90 на ОГ средней сложности

6 Определение MCS по всем структурам T-орграфа Набор орграфов в ЕО MCS, число вершин Экспон. р < 120 на ОГ средней сложности

7 Построение Ь-модели вида [V се НР'ш\ для каждого tGеTG и полупутей-фрагментов Набор орграфов в ЕО Матрица достроек вершин до HPw Экспон. р < 5000 на ОГ средней сложности и полупутях длины 2

8 Пересечение Ь-моделей вида [V Ше HPw\ для ОГ tгG1еTG1 и ОГ tjG2еTG2 Матрицы Ь- моделей для ОГ tгGlеTGl и ОГ tiG2еTG2 Значение А, SI2 Полином. р < 5000 на ОГ средней сложности и полупутях длины 2

9 Построение матрицы вкладов вершин в базисе НР'ш — фрагментов для каждого tGеTG и полупутей-фрагментов Орграф в ЕО Матрица вкладов вершин в базисе ЯРш — фрагментов Экспон. р < 5000 на ОГ средней сложности и полупутях длины 2

10 Вычисление ПСС, индексов и вектор-индексов сложности в базисе НР'ш — фрагментов для каждого tGеTG Орграф в ЕО Значения ПСС, индексов и вектор-индексов сложности Экспон. р<5000 на ОГ средней сложности и полупутях длины 2

П4.2. Автоматизированная система научных исследований «Мастерская граф-моделей»

АСНИ обеспечивает компьютерную поддержку СС-анализа систем и в научном плане ориентирована в первую очередь на решение задач определения сложности, сходства, формирования и исследования новых видов отношений толерантности, эквивалентности и подобия ГМС с главной целью - повышение

эффективности и расширения интеллектуальных возможностей современных компьютерных систем обработки структурной информации [12, 84, 108]. АСНИ позволяет проводить исследования по результатам решения следующих задач: 1) сравнение ГМС (изоморфизм, изоморфное вложение, изоморфное пересечение) с визуализацией и анимацией результатов; 2) определение сходства орграфов и T-орграфов; 3) вычисление ПСС, индексов и вектор-индексов сложности орграфов в базисах путей, полупутей и др. для орграфов и T-орграфов орграфов; 4) вычисление матриц вкладов фрагментов при использовании разных базисов СД для орграфов и T-орграфов; 5) построение надграфов путей и полупутей для орграфов и T-орграфов; 6) поиск ГМС, сходных с заданным шаблоном; 7) выделение кластеров в заданном множестве орграфов по результатам определения попарного сходства орграфов; 8) выделение кластеров фрагментов орграфа по результатам определения сходства расположения фрагментов; 9) автоматическая прорисовка диаграмм структур орграфов; 10) автоматическое выделение классов эквивалентности орграфов с определением чувствительности решения задачи различения по вычисленным характеристикам; 11) генерация и конструктивное перечисление ордеревьев, орграфов с заданными характеристиками; 12) определение экспериментальных оценок вычислительной сложности алгоритмов структурного анализа ГМС; 13) построение матриц вкладов фрагментов орграфов в заданные базисы СД; 14) определение попарного сходства орграфов на основе ¿-моделей; 15) определение попарного сходства расположения фрагментов орграфов с построением полного графа попарного сходства; 16) другие задачи анализа орграфов и T-орграфов. АСНИ построена по многокомпонентной технологии. К его ядру могут подключаться новые программы, библиотеки программ, расширяющие функциональное наполнение АСНИ. Авторские программные разработки выполнены именно в виде программ-расширений АСНИ. Структуры, с которыми работает АСНИ, организованы в базы структурной информации и базы результатов, полученных на основе экспериментов. На рис. П4.1 приведен пример главного окна АСНИ с открытой для исследования базой всех орграфов для p=5.

Количествен ное оп ределение сходства структур и отображение его в виде графа