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

Размещено на http://www.allbest.ru/

Государственный университет - Высшая Школа Экономики, Москва

Московский Энергетический Институт (Технический Университет), Москва

ПРОГРАММНЫЕ СРЕДСТВА ДЛЯ ПОСТРОЕНИЯ И ИССЛЕДОВАНИЯ МОДЕЛЕЙ СТРУКТУРНОЙ СЛОЖНОСТИ ОРГРАФОВ

А.А. Незнано, Ю.В. Старичкова

Аннотация

Рассмотрены оригинальные программные средства, реализующие построение и анализ системы моделей структурной сложности орграфов. Данные средства реализованы в виде подсистемы АСНИ «Graph Model Workshop» и нашли применение при исследовании сложности графовых моделей различных систем.

Введение

Исследуется сложность в классе ориентированных графов (орграфов). Актуальность исследования сложности в классе орграфов обусловлена тем, что данный класс графов имеет большое научное значение и широкое практическое применение (представление знаний, интеллектуальный анализ данных, распознавание образов, структурная лингвистика и другие). Многие проблемы искусственного интеллекта, извлечения знаний и машинного обучения рассматривают структурированные данные переменной размерности, такие как строки и различные последовательности, деревья и ориентированные и неориентированные графы. В качестве примера структурированных данных можно назвать: текст и документы; DNA/RNA-протеиновые последовательности и эволюционные деревья биоинформатики. Один из подходов анализа таких данных основан на графовых моделях, [Frey, 1998]; [Heckerman, 1997], является вероятностным методом, в котором случайные переменные ассоциируются с вершинами графа, а связи прямо соотносятся с Марковским предположением о независимости переменных. Граф обычно состоит из набора входных вершин, отражающих структуру (последовательность, граф и т.д.) входных данных, и выходных вершин, ассоциированных, например, с задачами классификации или регрессии. Графовые модели параметризуются локальными условными распределениями переменных узла относительно соседних узлов - например, узел относительно его родительского узла в случае Байесовских сетей. Чтобы обработать данные переменной размерности и формата, необходимо сделать ряд специфических предположений. Такие предположения на графах регулярной структуры, таких как цепи, деревья и решетки, обычно делаются относительно стационарности либо инвариантности перевода (например, динамические Байесовские сети). Большинство исследований по графовым моделям связано с выбором подходящих графов и случайных переменных, и распространением информации и знаний, которые в сложных моделях требуют серьезных вычислений.

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

В докладе рассматривается реализация методов построения и анализа индексов и вектор-индексов структурной спектральной сложности орграфов, а также моделей сложности из класса b-моделей.

1. Индексы структурной сложности орграфов в базисах ориентированных цепных фрагментов

Рассмотрим задачу нахождения индекса, вектор-индекса СС и полного структурного спектра (ПСС) орграфа G в базисе произвольных фрагментов. Вектор-индекс, индекс структурной сложности и ПСС орграфа G в базисе произвольных фрагментов [Кохов, 2002]:

,

,

,

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

Для разработки алгоритмов и дальнейших исследований в качестве мер сложности выбраны вектор-индексы, индексы СС и ПСС в базисе простых путей (ISSC(G/P)), полупутей (ISSC(G/PP)), контуров (ISSC(G/C)), полуконтуров (ISSC(G/CC)) и ориентированных цепных фрагментов (ОЦФ) (ISSC(G₁/OCF)).

ОЦФ - связный орграф, состоящей либо из одной вершины (ОЦФ длины 0, наименьший элемент базиса), либо из большего числа вершин, причем две из них имеют степень 1, а остальные - 2 (длина ОЦФ равна числу дуг в нём). Отметим, что полустепени исхода и захода могут быть любыми. Использования ОЦФ в качестве элементов базиса позволяет увеличить дискриминирующую способность индексов СС при сохранении вычислительной сложности алгоритмов построения индексов.

В таблице 1 приведен пример базовых ОЦФ и их значений сложности.

Табл. 1

Рис. 2 График чувствительности различения индексов сложности для планарных орграфов на 7 вершинах

2. Структурные модели сложности орграфов

программный орграф модель сложность

Кроме моделей СС в виде индексов и вектор-индексов, реализованы и более сложные структурные модели сложности - b-модели в базисе ОЦФ. Данный класс моделей СС впервые предложен Коховым В.А. [Кохов, 2002]. b-модель представляет собой двудольный граф со структурными весами на вершинах и рёбрах [Незнанов, 2005]. Левая доля - элементы базиса (то есть типы фрагментов орграфа); правая доля - помеченные фрагменты; ребро проводится в случае, если помеченный фрагмент, задаваемый весом вершины левой доли вкладывается во фрагмент, тип которого совпадает с типом, задаваемым весом вершины правой доли. Веса рёбер отражают либо число вложений, либо относительные вклады помеченных фрагментов в общую сложность орграфа. В сравнении с индексами и вектор-индексами СС b-модели имеют намного большую дискриминирующую способность, позволяют решать новые классы задач, но требуют больше памяти и имеют большую сложность построения. В таблице 3 приведен пример графов с эквивалентными значениями индекса СС ISSC(G₁/OCF) = ISSC(G₂/OCF) = 43, но имеющие различные b-модели. Прорисовка диаграмм выполнена идентичным методом для визуального сравнения.

Табл. 3

3. Программная реализация расширения построения индексов и вектор-индексов сложности

Программный комплекс «Сложность орграфов в ориентированных базисах» (далее - DCDB) предназначен для вычисления ПСС, вектор-индексов, индексов СС в базисе путей, полупутей, контуров, полуконтуров и ОЦФ орграфов с особой обработкой некоторых их подклассов (например, планарных орграфов). Он реализован в виде набора расширений АСНИ «Graph Model Workshop» (GMW).

Комплекс создан в среде Borland Developer Studio 2007 на языке Delphi. Объём авторского исходного кода DCDB - более 100 КБ, число строк исходного кода основных алгоритмов - 1288, всего компилируемых строк - 3170, объём машинного кода - 1391 КБ. Построенные модели структурной сложности хранятся в виде набора таблиц в базе данных результатов экспериментов GMW.

Параметризация построения индексов и вектор-индексов (рис. 3):

· тип базиса для вычисления индекса, вектор-индекса CC;

· длина максимального элемента базиса (для конструктивно перечисляемых базисов) или набор ОЦФ (для выбора базиса, задаваемого пользователем поэлементно);

· значения сложности минимальных элементов базиса (для конструктивно перечисляемых базисов с автоматическим расчётом сложности остальных элементов) или всех элементов.

Рис. 3 Интерфейс расширения АСНИ «Graph Model Workshop»

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

Исследована сложность орграфов с использованием индексов, вектор-индексов и b-моделей. Расширена функциональность АСНИ «Graph Model Workshop» программным комплексом «DCDB». Получены оценки чувствительности индексов СС, вектор-индексов, ПСС и b-моделей в базисах ОЦФ для планарных, бесконтурных, планарных бесконтурных и семейств орграфов.

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

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

2. Незнанов А.А. Методы и программные средства для различения расположения фрагментов графовых моделей систем: дис. кан. тех. наук. М.: МЭИ (ТУ), 2005.

3. Frey B. J., Lawrence N., Bishop C. M. Markovian interence in belief networks. Presented at Learning, Machines that Learn or what some people call Snowbird, Snowbird, Utah, April, 1998.

4. Heckerman D. "Bayesian Networks for Data Mining". Data Mining and Knowledge Discovery. 1997. № 1.

Размещено на Allbest.ru