Рассмотрение системы стратификации моделей, позволяющей определять и исследовать широкий спектр отношений на структурах систем. Создание обобщенного подструктурного подхода к анализу сходства графов. Новые виды отношений эквивалентности и толерантности.
Аннотация к работе
Сходство структур систем является ключевым понятием в реализации правдоподобных рассуждений, что определяет актуальность и значимость разработки моделей, методов и программных комплексов для анализа сходства и подобия структурированных нечисловых объектов (графов, мультиграфов, семантических сетей и др.) [Финн, 1991], [Кохов и др., 2004]. g-модели для характеризации сходства расположения фрагментов в графе Под графом отношений фрагментов (g-моделью) графа G = (V, E) будем понимать двудольный граф с весами на вершинах и ребрах вида: GM_sr(G) = WLEFLWLL(sr)FLWLR(G) = (VLEVR,sr,E,WVL,WL,WVR,WR,WE,we), определяемый параметрами sr, BL, BR, EL, ER, где: 1. sr - бинарное отношение на множестве Ml, то есть sr I (Ml ? Ml); EL - функция, определяющая тип вложения фрагментов из BL в граф G (EL(ft):M®G (как фрагмент); EL(ft):M®SG (как подграф)); Введем систему обозначения g-моделей [Кохов, 2004]: [we[l ]]L[WL[l ]](sr)R[WR[l ]] = [w[l ]]L[w[l ]](sr)R[w[l ]], где L обозначает множество WVL, R - множество WVR, sr - отношение, определенное на WVL?WVR; we - наличие графов-весов ребер g-модели, WL (WR) - наличие графов-весов вершин левой (правой) доли g-модели; l - наличие пометок вершин в графах-весах. Если учесть орбиты Q(Autt(G), fit) группы Autt(G), определяющие симметрию расположения фрагментов типа t в графе G, для t=1, 2,…, T, то выделим новый вид g-и gs-моделей, учитывающих число фрагментов в орбите (второй вес вершины (WVN(v)) в g-модели) и характеризующих сходство расположения фрагментов с точностью до орбит групп Autt(G).Предложенные модели позволили разработать обобщенный подструктурный подход к анализу сходства структур систем, учитывающий сходство расположения фрагментов.
Введение
Сходство структур систем является ключевым понятием в реализации правдоподобных рассуждений, что определяет актуальность и значимость разработки моделей, методов и программных комплексов для анализа сходства и подобия структурированных нечисловых объектов (графов, мультиграфов, семантических сетей и др.) [Финн, 1991], [Кохов и др., 2004].
g-модели для характеризации сходства расположения фрагментов в графе
Пусть M - множество графов, Ml - множество помеченных графов, F(G)=(F1,F2,…,Ft,…,FT ) (Fl(G)={Fl1,Fl2,…,Flt,…,FLT }) - множество всех собственных фрагментов (помеченных фрагментов) графа G = (V, E), а Flt={f1lt, f2lt, …, fjlt, …, frtlt} - множество помеченных фрагментов типа t, где j - номер фрагмента, rt - число фрагментов типа t, T - число типов.
Под графом отношений фрагментов (g-моделью) графа G = (V, E) будем понимать двудольный граф с весами на вершинах и ребрах вида: GM_sr(G) = WLEFLWLL(sr)FLWLR(G) = (VLEVR,sr,E,WVL,WL,WVR,WR,WE,we), определяемый параметрами sr, BL, BR, EL, ER, где: 1. sr - бинарное отношение на множестве Ml, то есть sr I (Ml ? Ml);
2. BL - базис левой доли (множество фрагментов левой доли);
3. BR - базис правой доли (множество фрагментов правой доли);
4. EL - функция, определяющая тип вложения фрагментов из BL в граф G (EL(ft):M®G (как фрагмент); EL(ft):M®SG (как подграф));
5. ER - функция, определяющая тип вложения фрагментов из BR в граф G (ER(ft):M®G (как фрагмент); ER(ft):M®SG (как подграф));
6. VL - множество вершин левой доли (VIVL соответствует одному из помеченных фрагментов - канонических вложений элементов из BL в G);
7. VR - множество вершин правой доли (VIVR соответствует одному из помеченных фрагментов - канонических вложений элементов из BR в G);
8. E - множество ребер: "VIVL, "UIVR [{v,u}IE U WL(v)(sr)WR(u)];
9. WVL - множество весов вершин левой доли (WVL I Ml );
10. WL - функция, сопоставляющая вершинам VL их веса (WL:VL®WVL);
11. WVR - множество весов вершин правой доли (WVR I Ml );
12. WR - функция, сопоставляющая вершинам VR их веса (WR:VR®WVR);
13. WE - множество весов ребер (WE I Ml или WE I N);
14. WE - функция, сопоставляющая веса ребрам (WE:E®WE).
Введем систему обозначения g-моделей [Кохов, 2004]: [we[l ]]L[WL[l ]](sr)R[WR[l ]] = [w[l ]]L[w[l ]](sr)R[w[l ]], где L обозначает множество WVL, R - множество WVR, sr - отношение, определенное на WVL?WVR; we - наличие графов-весов ребер g-модели, WL (WR) - наличие графов-весов вершин левой (правой) доли g-модели; l - наличие пометок вершин в графах-весах. При отсутствии некоторых параметров, выделенных скобками [ ], получаются различные виды g-моделей. При совпадении WL и WR доли g-модели «склеиваются» в одну.
Отношение sr определяется типом операции над парой (filt1, fjlt2) и ограничениями на ее операнды и результат. В качестве операции выделим операцию определения максимального изоморфного пересечения (МИП), результатом которой является максимальный общий фрагмент (МОФ): mcf(filt1, fjlt2) ? filt1Cfjlt2. Для помеченных фрагментов МОФ определяется однозначно и результатом может быть ?. Ограничения на операнды (предикат допустимости PO(filt1, fjlt2)) определяют диапазоны возможного изменения соотношений между filt1 и fjlt2. Ограничения на результат (предикат PMCF(filt1Cfjlt2,filt1,fjlt2)) определяют изменения диапазона параметров МОФ и соотношений между МОФ и исходными фрагментами: filt1Cfjlt2 U PO(filt1, fjlt2) & PMCF(filt1Cfjlt2, filt1, fjlt2).
Определение 1. Матрицей M_GM(G) = ||mcfij||, i=1,2,…,k; j=1,2,…,k смежности вершин g-модели WLEFLWLLCFLWR(G) = WLEFLWLCFLW(G) называется матрица, для которой mcf lij - максимальное по числу вершин изоморфное пересечение filt1Cfjlt2, если fi lt1Cfj lt2 ? ? и 0, если FILMCFJLN = ?.
Рассмотрим g-модель WEFLWCFLW(G), в которой структурный вес we каждого ребра заменим на D1(fi lt1, fj lt2) = |V(fi lt1)| |V(fjlt2)| - 2|V(mcfij)| или D2(fi lt1,fj lt2)=|V(fi lt1)| |E(filt1)| |V(fj lt2)| |E(fj lt2)|-2(|V(mcf(fi lt1,fj lt2))| |E(mcf(fi lt1,fj lt2))|).
В результате построена gs-модель WDFLWCFLW(G), характеризующая сходство расположения фрагментов fjl I Fl в графе G по D1 или D2.
Если учесть орбиты Q(Autt(G), fit) группы Autt(G), определяющие симметрию расположения фрагментов типа t в графе G, для t=1, 2,…, T, то выделим новый вид g- и gs-моделей, учитывающих число фрагментов в орбите (второй вес вершины (WVN(v)) в g-модели) и характеризующих сходство расположения фрагментов с точностью до орбит групп Autt(G). Обозначим соответственно эти модели как go-модели и gso-модели.
На рис. 1 приведены примеры диаграмм семи моделей. Результаты определения МОФ для подграфов С3 и С4 с учетом расположения их орбит в графе G и расстояния между орбитами приведены в табл. 1-3.
Определим систему стратификации gs-моделей, которая необходима для: (1) обобщения известных отношений подобия, толерантности и эквивалентности графов и выделения новых видов этих отношений; (2) выделения моделей, для которых задачи построения и исследования имеют существенно меньшую вычислительную сложность, чем для gs-модели общего вида; (3) построения на основе gs-моделей иерархической системы структурных и числовых инвариантов с целью систематического исследования их чувствительности при решении задач различения графов (расположения фрагментов в графе), определения сложности и сходства графов с учетом расположения фрагментов.
Предлагаемая система включает четыре разреза стратификации: (1) по виду операндов операции C и видам иерархии их рассмотрения, ограничениям на вид и результат операции; (2) По признаку выделения отдельных фрагментов gs-модели; (3) по признаку учета или не учета структурных весов вершин и/или ребер gs-модели и видам структурных весов; (4) по частному виду операции C (вложение, изоморфизм).
В качестве параметров первого разреза стратификации выделим: 1. Вид операции, определяющей отношение sr=C, с учетом видов фрагментов структурных весов вершин gs-модели как частей графа (пересечение общего вида - C, пересечение вида подграф-подграф - CS).
2. Признак связности или несвязности графа, соответствующего весу (WL[l]) левой доли или/и весу правой доли (WR[l]) gs-модели (CC, Cc, CCC).
3. Высоту окрестности o(film) относительно фрагмента film(WL), которая вычисляется от 1 до e, где e - эксцентриситет фрагмента. Результаты пересечения с fjln рассматриваются относительно этой высоты.
4. Вид фрагментов, задающих структурные веса (WL[l]) левой или/и веса правой доли (WR[l]) gs-модели (без циклов - FT, с циклами - F и др.).
5. Величину ранга rn(film) (веса вершин левой доли gs-модели).
6. Разность рангов r=irn(film) - rn(fjln)c: r=q; r=q-1;…; r=2; r=1 (r=p; r=p-1;…; r=2; r=1) и вид соотношения фрагментов долей gs-модели.
7. Число компонент связности кс в фрагменте-пересечении mcf lij: kc>1 (любое пересечение); кс=1 (связное пересечение - Cc).
G C3 C4 g(G)=WCSL3-4w C go(G)=WCSL3-4wn CQ gs(G)=WD1CSL3-4w C gso(G)=WD1CSL3-4wn CQ g(G)=HWCSL3-4 w CQ gso(G)=HWD1С3-4WNCQ gso(G)=HWD1С3-4 n CQ
Рис. 1 Граф, анализируемые подграфы типа C3, C4 и примеры моделей
Третий параметр приводит к выделению иерархических g-моделей. Это актуально с позиций исследования полноты локальных функций, и имеет как, теоретический, так и прикладной интерес, связанный с построением эффективных алгоритмов анализа.
Табл. 1
Автоморфизмы и орбиты групп , Автоморфизмы
1 2 3 4 5 6
1 (1,2,3) (1,3,5) (1,4,5) (2,3,7) (2,6,7) (3,5,7)
2 (1,2,3) (2,3,7) (2,6,7) (1,3,5) (1,4,5) (3,5,7)
3 (3,5,7) (1,3,5) (1,4,5) (2,3,7) (2,6,7) (1,2,3)
4 (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
1 (1,2,7,5) (1,2,7,5)
Табл. 2
Матрица пересечений пар помеченных подграфов С3 и С4
Матрица МИП C3 с C4 (p,q) в МИП C3 с C4 D1
1 1 1
( 1,2,7,5 ) ( p, q ) D1
1 ( 1,2,3 ) 12 1 2, 1 3
2 ( 1,3,5 ) 15 2 2, 1 3
3 ( 1,4,5 ) 15 3 2, 1 3
4 ( 2,3,7 ) 27 4 2, 1 3
5 ( 2,6,7 ) 27 5 2, 1 3
6 ( 3,5,7 ) 57 6 2, 1 3
(p,q) в МИП C3 с C3 (выше главной диагонали), и значения D1 (ниже главной диагонали)
Определение 2. Матрицей смежности вершин иерархической gs-модели HRWLFLWLC(G) окружения r называется матрица M_H(G)=||mcf lij||; i=1,2,…,k; j=1,2,…,k; для которой mcf lij - максимальное по числу ребер изоморфное пересечение FILMCFJLN, если (FILMCFJLN)??U(rn(film) =urn(fjln)-rc), и 0 (или граф межфрагментного соединения) - в противном случае.
В соответствии со значением r различаем три класса gs-моделей: локальные (r=lk=1), квазиглобальные (1<r=kg<e), глобальные (r=gl=e).
Табл. 3
Матрицы пересечений орбит подграфов С3,С4, размеры пересечений и расстояния D1 между орбитами
12,5715,2715,27
Q1 Q2 Q3
Q1 Q2 Q3 2,1
Орбиты фрагментов, составляющих mcf(С3,С4)
Расстояния между орбитами
D1 Q1 Q2 Q3
Q1 3 3 3
Орбиты фрагментов, составляющих mcf(С3,С3)
Расстояния между орбитами
D1 Q1 Q2 Q3
Q1 0 2 4
Q2 2 0 2
Q3 4 2 0
При рассмотрении четвертого параметра возможны два подхода: от самых сложных (примарных по вершинам или ребрам) до самых простых, рассматривая последовательно примарные от примарных;
от самых несложных фрагментов (вершины (V), ребра (Е), цепи (Pc), деревья (Tr), леса (Fr)) до самых сложных, рассматривая фрагменты с учетом монотонного роста их индексов сложности [Кохов, 2002].
Новые классы отношений эквивалентности и толерантности графов с учетом сходства расположения фрагментов
Пусть заданы gs1=w1DF1lw1CF1lw1=(V1LEV1R,C,E1,WV1L,WV1R,WE1) и gs2=w2DF2lw2CF2lw2=(V2LEV2R,C,E2,WV2L,WV2R,WE2).
Определение 3. gs1 и gs2 изоморфны (gs1»gs2), если существуют взаимнооднозначные соответствия j: V1L « V2L и d: V1R «V2R, такие что "VIIV1L,"UJIV1R:{vi,uj}IE1U(({j(vi),d(uj)}IE2)U(WE1{vi,uj}=WE2{j(vi),d(uj)}));
Определение 5. Модели gso1 и gso2 изоморфны (gso1»gso2), если существуют 1-1 соответствия j: V1L « V2L и d: V1R «V2R, такие что "VIIV1L,"UJIV1R:{vi,uj}IE1U (({j(vi),d(uj)}IE2) U (WE1{vi,uj} = WE2{j(vi),d(uj)}));
Определение 6. Графы Gi и Gi эквивалентны по gso-модели WDFLWCNQ, если выполняется условие (WDFLWCNQ(Gi))»(WDFLWCNQ(Gi)).
Система стратификации gso-моделей позволяет определять и исследовать широкий спектр отношений эквивалентности (изоморфизм gso-моделей) и сходства (МИП gso-моделей) с учетом сходства расположения фрагментов графа. На рис. 2 приведены примеры новых видов отношений эквивалентности графов.
10_50 10_108 HWD1CSL3-5WC n QS
Изоциклические графы HWD2Cl3-4w C n Q
Рис. 2 Примеры графов с одинаковым сходством расположения орбит фрагментов
Обобщенный подструктурный подход на основе стратифицированной системы g-моделей
Использование расширяемой по числу анализируемых фрагментов системы g-моделей, приводит к новым аспектам исследования сходства и новым характеристикам сходства: 1. 2.
3.
4. где dcp - среднее расстояние между графами; мср - индекс среднего сходства между графами; d(Gi,Gj/B) - расстояние между векторами расстояний (V_d); m(Gi,Gj/B) - расстояния между векторами индексов сходства (V_m).
На рис. 3 приведены графы, их g-модели, а на рис. 4 приведены графики изменения сходства пар анализируемых графов при использовании системы расширяемых по длине цепей g-моделей.
G1 G2 G3
HP0-1lc WIPLCW(G)
. . .
HP0-4lc WIPLCW(G)
Рис. 3 Графы и их иерархические g-модели
Рис. 4 График изменения расстояний D1 между парами графов на основе МИП g-моделей b-модели для характеризации сходства расположения фрагментов в графе
Если в gs-модели вместо операции C использовать операцию I и вместо помеченных фрагментов-весов для вершин правой доли использовать их типы (непомеченные фрагменты), то в результате будут построены 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.