Отзыв ведущей организации (Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов)

«УТВКРЖДАЮ» Заместитель директора по научной работе Федерального государственного учреждения «Федеральный исследовательский центр , ~информатика и управление» РАН» .";"'" ''докйр, хн ких к "'""'М ный 2016 г. ОТЗЫВ ВЕДУЩЕЙ ОРГАНИЗАЦИИ на дисссртацинз Кохова Виктора Викторовича «Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов», представленную на соискание ученой степени кандидата технических наук по специальности 05.13.17 — «Теоретические основы информатики» Актуальность темы диссертации.

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

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

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

В настоящее время управление структурой КСС вЂ” новая актуальная область менеджмента. Таким образом, актуальность работы не вызывает сомнений. Структура диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и пяти приложений. Вводнпя глава посвящена обоснованию актуальности темы, формулировке целей и задач исследования, описывается научная новизна и практическая значимость результатов диссертации. В иервой главе дан обзор методов определения сходства графовых моделей данных и выделены 3 основных подхода к решению: а) подструктурный подход (П-подход) с использованием максимальных общих фрагментов, Ь) обобщенный П-подход, использующий трансграфы цепей для графов и путей для ациклических структур, с) структурно-характеристический подход (СХ- подход), использующий три вида моделей сложности, которые обобщают скалярные, векторные и матричные инварианты ациклических структур.

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

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

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

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

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

Кроме того, сформулированы 3 гипотезы, обобщающие выше указанного изоморфизма на весь класс орграфов, которые получили подтверждение при проверке на всех ордеревьях, всех орграфах без контуров и всех орграфах с числами вершин соответственно до 15, 8, 7 (проанализировано 15 282 014 орграфов). Вторым значимым научным результатом главы является обоснование корректности алгоритма сведения задачи распознавания изоморфизма надграфов полупутей двух орграфов к распознаванию изоморфизма их исходных орграфов, что позволило впервые выделить представительные подклассы двудольных ор графов большого порядка 1десятки и сотни тысяч вершин), для которых два вида задач определения сходства (точное сходство — изоморфизм, частичное точное сходство — изоморфное вложение) .имеют полиномиальную вычислительную сложность, если эти задачи имеют полиномиальную вычислительную сложность на исходных орграфах.

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

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

Описаны параметры программного комплекса, реализующего предложенные методы исследования Т-орграфов. В заключении приведены основные результаты, полученные в работе. В приложения вынесены: алгоритм определения сходства ордеревьев, экпериментальные оценки вычислительной сложности разработанных алгоритмов, перечень программ, входящих в созданные автором 2 комплекса программ, примеры областей применения методов определения сходства орграфов и сходства Т-орграфов, примеры решения тестовых задач при внедрении результатов и акты о внедрении в НИИСИ РАН и компанию ООО «Терминал - Сервис». Научная новизна исследований. В работе получены следующие научные результаты.

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

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