Граф-модели для определения сходства структур систем с учетом сходства расположения фрагментов

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

ГРАФ-МОДЕЛИ ДЛЯ ОПРЕДЕЛЕНИЯ СХОДСТВА СТРУКТУР СИСТЕМ С УЧЕТОМ СХОДСТВА РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ

В.А. Кохов

Аннотация

граф стратификационный модель система

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

Введение

Сходство структур систем является ключевым понятием в реализации правдоподобных рассуждений, что определяет актуальность и значимость разработки моделей, методов и программных комплексов для анализа сходства и подобия структурированных нечисловых объектов (графов, мультиграфов, семантических сетей и др.) [Финн, 1991], [Кохов и др., 2004].

g-модели для характеризации сходства расположения фрагментов в графе

Пусть M множество графов, M^l множество помеченных графов, F(G)=(F¹,F²,…,F^t,…,F^T ) (F^l(G)={F^l1,F^l2,…,F^lt,…,F^lT }) - множество всех собственных фрагментов (помеченных фрагментов) графа G = (V, E), а F^lt={f₁^lt, f₂^lt, …, f_j^lt, …, f_rt^lt} множество помеченных фрагментов типа t, где j номер фрагмента, rt число фрагментов типа t, T число типов.

Под графом отношений фрагментов (g-моделью) графа G = (V, E) будем понимать двудольный граф с весами на вершинах и рёбрах вида:

GM_sr(G) = w^l_eF^lw^l_L(sr)F^lw^l_R(G) = (V_LV_R,sr,E,WV_L,w_L,WV_R,w_R,WE,w_e),

определяемый параметрами sr, B_L, B_R, E_L, E_R, где:

1. sr - бинарное отношение на множестве M^l, то есть sr (M^l M^l);

2. B_L - базис левой доли (множество фрагментов левой доли);

3. B_R - базис правой доли (множество фрагментов правой доли);

4. E_L - функция, определяющая тип вложения фрагментов из B_L в граф G (E_L(f^t):MG (как фрагмент); E_L(f^t):M^SG (как подграф));

5. E_R - функция, определяющая тип вложения фрагментов из B_R в граф G (E_R(f^t):MG (как фрагмент); E_R(f^t):M^SG (как подграф));

6. V_L - множество вершин левой доли (vV_L соответствует одному из помеченных фрагментов - канонических вложений элементов из B_L в G);

7. V_R - множество вершин правой доли (vV_R соответствует одному из помеченных фрагментов - канонических вложений элементов из B_R в G);

8. E - множество рёбер: vV_L, uV_R [{v,u}E w_L(v)(sr)w_R(u)];

9. WV_L - множество весов вершин левой доли (WV_L M^l );

10. w_L - функция, сопоставляющая вершинам V_L их веса (w_L:V_LWV_L);

11. WV_R - множество весов вершин правой доли (WV_R M^l );

12. w_R - функция, сопоставляющая вершинам V_R их веса (w_R:V_RWV_R);

13. WE - множество весов ребер (WE M^l или WE N);

14. w_E - функция, сопоставляющая веса рёбрам (w_E:EWE).

Введем систему обозначения g-моделей [Кохов, 2004]:

[w_e^{[l ]}]L[w_L^{[l ]}](sr)R[w_R^{[l ]}] = [w^{[l ]}]L[w^{[l ]}](sr)R[w^{[l ]}],

где L обозначает множество WV_L, R - множество WV_R, sr - отношение, определенное на WV_LWV_R; w_e - наличие графов-весов ребер g-модели, w_L (w_R) - наличие графов-весов вершин левой (правой) доли g-модели; l - наличие пометок вершин в графах-весах. При отсутствии некоторых параметров, выделенных скобками [ ], получаются различные виды g-моделей. При совпадении w_L и w_R доли g-модели «склеиваются» в одну.

Отношение sr определяется типом операции над парой (f_i^lt1, f_j^lt2) и ограничениями на её операнды и результат. В качестве операции выделим операцию определения максимального изоморфного пересечения (МИП), результатом которой является максимальный общий фрагмент (МОФ): mcf(f_i^lt1, f_j^lt2) ? f_i^lt1f_j^lt2. Для помеченных фрагментов МОФ определяется однозначно и результатом может быть . Ограничения на операнды (предикат допустимости P_O(f_i^lt1, f_j^lt2)) определяют диапазоны возможного изменения соотношений между f_i^lt1 и f_j^lt2. Ограничения на результат (предикат P_MCF(f_i^lt1f_j^lt2,f_i^lt1,f_j^lt2)) определяют изменения диапазона параметров МОФ и соотношений между МОФ и исходными фрагментами:

f_i^lt1f_j^lt2 P_O(f_i^lt1, f_j^lt2) & P_MCF(f_i^lt1f_j^lt2, f_i^lt1, f_j^lt2).

Определение 1. Матрицей M_GM(G) = ||mсf_ij||, i=1,2,…,k; j=1,2,…,k смежности вершин g-модели w^l_eF^lw^l_LF^lw_R(G) = w^l_eF^lw^lF^lw(G) называется матрица, для которой mсf ^l_ij максимальное по числу вершин изоморфное пересечение f_i^lt1f_j^lt2, если f_i ^lt1f_j ^lt2 и 0, если f_i^lmf_j^ln = .

Рассмотрим g-модель w_eF^lwF^lw(G), в которой структурный вес w_e каждого ребра заменим на D1(f_i ^lt1, f_j ^lt2) = |V(f_i ^lt1)| + |V(f_j^lt2)| 2|V(mсf_ij)| или D2(f_i ^lt1,f_j ^lt2)=|V(f_i ^lt1)|+|E(f_i^lt1)|+|V(f_j ^lt2)|+|E(f_j ^lt2)|2(|V(mcf(f_i ^lt1,f_j ^lt2))|+|E(mcf(f_i ^lt1,f_j ^lt2))|).

В результате построена gs-модель w^DF^lwF^lw(G), характеризующая сходство расположения фрагментов f_j^l F^l в графе G по D1 или D2.

Если учесть орбиты (Aut^t(G), f_i^t) группы Aut^t(G), определяющие симметрию расположения фрагментов типа t в графе G, для t=1, 2,…, T, то выделим новый вид g- и gs-моделей, учитывающих число фрагментов в орбите (второй вес вершины (WVN(v)) в g-модели) и характеризующих сходство расположения фрагментов с точностью до орбит групп Aut^t(G). Обозначим соответственно эти модели как go-модели и gso-модели.

На рис. 1 приведены примеры диаграмм семи моделей. Результаты определения МОФ для подграфов С₃ и С₄ с учетом расположения их орбит в графе G и расстояния между орбитами приведены в табл. 1-3.

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

Предлагаемая система включает четыре разреза стратификации: (1) по виду операндов операции и видам иерархии их рассмотрения, ограничениям на вид и результат операции; (2) По признаку выделения отдельных фрагментов gs-модели; (3) по признаку учета или не учета структурных весов вершин и/или ребер gs-модели и видам структурных весов; (4) по частному виду операции (вложение, изоморфизм).

В качестве параметров первого разреза стратификации выделим:

1. Вид операции, определяющей отношение sr=, с учетом видов фрагментов структурных весов вершин gs-модели как частей графа (пересечение общего вида - , пересечение вида подграф-подграф - ^S).

2. Признак связности или несвязности графа, соответствующего весу (w_L^[l]) левой доли или/и весу правой доли (w_R^[l]) gs-модели (^с, ^с, ^сс).

3. Высоту окрестности o(f_i^lm) относительно фрагмента f_i^lm(w_L), которая вычисляется от 1 до e, где e - эксцентриситет фрагмента. Результаты пересечения с f_j^ln рассматриваются относительно этой высоты.

4. Вид фрагментов, задающих структурные веса (w_L^[l]) левой или/и веса правой доли (w_R^[l]) gs-модели (без циклов - FT, с циклами - F и др.).

5. Величину ранга rn(f_i^lm) (веса вершин левой доли gs-модели).

6. Разность рангов r=rn(f_i^lm) rn(f_j^ln): r=q; r=q1;…; r=2; r=1 (r=p; r=p1;…; r=2; r=1) и вид соотношения фрагментов долей gs-модели.

7. Число компонент связности kс в фрагменте-пересечении mсf ^l_ij: kс>1 (любое пересечение); kс=1 (связное пересечение - _с).

Рис. 1 Граф, анализируемые подграфы типа C3, C4 и примеры моделей

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

Табл. 1

Автоморфизмы и орбиты групп ,

Табл. 2

Матрица пересечений пар помеченных подграфов С₃ и С₄

Определение 2. Матрицей смежности вершин иерархической gs-модели H^rw^lF^lw^l(G) окружения r называется матрица M_H(G)=||mсf ^l_ij||; i=1,2,…,k; j=1,2,…,k; для которой mсf ^l_ij максимальное по числу ребер изоморфное пересечение f_i^lmf_j^ln, если (f_i^lmf_j^ln)(rn(f_i^lm) =rn(f_j^ln)r), и 0 (или граф межфрагментного соединения) - в противном случае.

В соответствии со значением r различаем три класса gs-моделей: локальные (r=lk=1), квазиглобальные (1<r=kg<e), глобальные (r=gl=e).

Табл. 3

Матрицы пересечений орбит подграфов С3,С4, размеры пересечений и расстояния D1 между орбитами

При рассмотрении четвертого параметра возможны два подхода:

от самых сложных (примарных по вершинам или ребрам) до самых простых, рассматривая последовательно примарные от примарных;

от самых несложных фрагментов (вершины (V), ребра (Е), цепи (P^c), деревья (Tr), леса (Fr)) до самых сложных, рассматривая фрагменты с учетом монотонного роста их индексов сложности [Кохов, 2002].

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

Пусть заданы gs₁=w₁^DF₁^lw₁F₁^lw₁=(V_1LV_1R,,E₁,WV_1L,WV_1R,WE₁) и

gs₂=w₂^DF₂^lw₂F₂^lw₂=(V_2LV_2R,,E₂,WV_2L,WV_2R,WE₂).

Определение 3. gs₁ и gs₂ изоморфны (gs₁gs₂), если существуют взаимнооднозначные соответствия : V_1L V_2L и : V_1R V_2R, такие что

v_iV_1L,u_jV_1R:{v_i,u_j}E₁(({(v_i),(u_j)}E₂)(WE₁{v_i,u_j}=WE₂{(v_i),(u_j)}));

WV_1L(v_i)WV_2L((v_i)); WV_1R(u_j)WV_2R((u_j)), i=1,2…,р_L=V_1L, j=1,2,…,р_R=V_1R.

Определение 4. Графы G_i и G_i эквивалентны по gs-модели w^DF^lwF^lw, если выполняется условие (w^DF^lwF^lw(G_i))(w^DF^lwF^lw(G_i)).

Пусть заданы gso₁=w₁^DF₁^lw_1n= (V_1LV_1R, E₁,WV_1L,WVN_1L,WV_1R,WVN_1R,WE₁) и gso₂= w₂^DF₂^lw_2n=(V_2LV_2R, E₂, WV_2L, WVN_2L, WV_2R, WVN_2R, WE₂).

Определение 5. Модели gso₁ и gso₂ изоморфны (gso₁gso₂), если существуют 1-1 соответствия : V_1L V_2L и : V_1R V_2R, такие что

v_iV_1L,u_jV_1R:{v_i,u_j}E₁ (({(v_i),(u_j)}E₂) (WE₁{v_i,u_j} = WE₂{(v_i),(u_j)}));

WV_1L(v_i) WV_2L((v_i)); WV_1R(u_j) WV_2R((u_j)); WVN_1L(v_i) = WVN_2L((v_i));

WVN_1R(u_j) = WVN_2R((u_j)), где i=1, 2, …, р_L =V_1L, j=1, 2, …, р_R =V_1R.

Определение 6. Графы G_i и G_i эквивалентны по gso-модели w^DF^lw_n, если выполняется условие (w^DF^lw_n(G_i))(w^DF^lw_n(G_i)).

Система стратификации gso-моделей позволяет определять и исследовать широкий спектр отношений эквивалентности (изоморфизм gso-моделей) и сходства (МИП gso-моделей) с учетом сходства расположения фрагментов графа. На рис. 2 приведены примеры новых видов отношений эквивалентности графов.

Рис. 2 Примеры графов с одинаковым сходством расположения орбит фрагментов

Обобщенный подструктурный подход на основе стратифицированной системы g-моделей

Использование расширяемой по числу анализируемых фрагментов системы g-моделей, приводит к новым аспектам исследования сходства и новым характеристикам сходства:

где d_ср среднее расстояние между графами; _ср индекс среднего сходства между графами; d(G_i,G_j/B) расстояние между векторами расстояний (V_d); (G_i,G_j/B) расстояния между векторами индексов сходства (V_).

На рис. 3 приведены графы, их g-модели, а на рис. 4 приведены графики изменения сходства пар анализируемых графов при использовании системы расширяемых по длине цепей g-моделей.

Рис. 3 Графы и их иерархические g-модели

Рис. 4 График изменения расстояний D1 между парами графов
на основе МИП g-моделей

b-модели для характеризации сходства расположения фрагментов в графе

Если в gs-модели вместо операции использовать операцию и вместо помеченных фрагментов-весов для вершин правой доли использовать их типы (непомеченные фрагменты), то в результате будут построены b-модели [4]. Эти модели позволили: (1) определить более широкий спектр отношений толерантности и эквивалентности графов на основе перехода от орбит расположения фрагментов к классам их эквивалентного расположения, задаваемым базисами структурных дескрипторов (СД); (2) анализировать точность характеризации расположения фрагментов в монотонно расширяемых по значениям индексов сложности базисах СД; (3) заменить экспоненциальный по вычислительной сложности алгоритм определения максимального общего фрагмента gs-моделей на эффективный алгоритм определения максимального общего фрагмента b(gs)-моделей [Кохов, 2002].

Заключение

Предложенные модели позволили разработать обобщенный подструктурный подход к анализу сходства структур систем, учитывающий сходство расположения фрагментов. На основе этих моделей стало возможным эффективное решение задачи определения сходства графов с учетом сходства расположения фрагментов методом замены поиска максимальных общих фрагментов для gs_моделей
(50-70 вершин) на поиск максимальных общих фрагментов для b(gs)_моделей (300-400 вершин).

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

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

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

3. [Кохов, 2004] Кохов В.А. Граф-модели в структурном спектральном анализе систем. // Труды международной научно-технической конференции «Информационные средства и технологии». (МФИ-2004), Т.1. Москва, 2004.

4. [Финн, 1991] Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ. // Итоги науки и техники, сер. «Информатика», Т.15. 1991.

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