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

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

G C3 C4	g (G)=wСSl3−4w.
go (G)=wСSl3−4wn.	gs (G)=wD1СSl3−4w.
gso (G)=wD1СSl3−4wn.	g (G)=HwСSl3−4 w.
gso (G)=HwD1С3−4wn.	gso (G)=HwD1С3−4 n.

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

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

Табл. 1.

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

Автоморфизмы.
	(1,2,3).	(1,3,5).	(1,4,5).	(2,3,7).	(2,6,7).	(3,5,7).
	(1,2,3).	(2,3,7).	(2,6,7).	(1,3,5).	(1,4,5).	(3,5,7).
	(3,5,7).	(1,3,5).	(1,4,5).	(2,3,7).	(2,6,7).	(1,2,3).
	(3,5,7).	(2,3,7).	(2,6,7).	(1,3,5).	(1,4,5).	(1,2,3).
Орбиты группы.
(1,2,3) (3,5,7).	(1,3,5) (2,3,7).	(1,4,5) (2,6,7).
Автоморфизмы.	Орбиты.
	(1,2,7,5).	(1,2,7,5).

Табл. 2.

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

Матрица МИП C3 с C4	(p, q) в МИП C3 с C4	D1.
	(1,2,7,5).		(p, q).	D1.
	(1,2,3).			2, 1.
	(1,3,5).			2, 1.
	(1,4,5).			2, 1.
	(2,3,7).			2, 1.
	(2,6,7).			2, 1.
	(3,5,7).			2, 1.
(p, q) в МИП C3 с C3 (выше главной диагонали),. и значения D1 (ниже главной диагонали).
	(1, 2, 3).	(1, 3, 5).	(1, 4, 5).	(2, 3, 7).	(2, 6, 7).	(3, 5, 7).
(1,2,3).		2, 1.	1, 0.	2, 1.	1, 0.	1, 0.
(1,3,5).			2, 1.	1, 0.		2, 1.
(1,4,5).						1, 0.
(2,3,7).					2, 1.	2, 1.
(2,6,7).						1, 0.
(3,5,7).

Определение 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.

Табл. 3.

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

	12,57.	15,27.	15,27.
			2,1.
Орбиты фрагментов, составляющих mcf (С3, С4).
Расстояния между орбитами.
D1.
	Орбиты фрагментов, составляющих mcf (С3, С3).
Расстояния между орбитами.
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 приведены примеры новых видов отношений эквивалентности графов.

1050 10108.	HwD1CSl3−5w n S
Изоциклические графы.	HwD2Cl3−4w n

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

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

1.		2.
3.
4.

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

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

G1	G2	G3
HP0−1lc wPlcw (G).
.. .
HP0−4lc wPlcw (G).

Рис. 3 Графы и их иерархические 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.