СТВОЛОВЫЕ СЕТИ : МАТЕМАТИЧЕСКИЕ АСПЕКТЫ А.А. Тихомиров (Москва, Международная академия информатизации) А.И. Труфанов, Л.Л. Носырева, Е.В. Носырева (Иркутск, - презентация

1 СТВОЛОВЫЕ СЕТИ : МАТЕМАТИЧЕСКИЕ АСПЕКТЫ А.А. Тихомиров (Москва, Международная академия информатизации) А.И. Труфанов, Л.Л. Носырева, Е.В. Носырева (Иркутск, Иркутский государственный технический университет )

2 Введение 1.Унарные операции 2.Операции над слоями 3.Бинарные операции над сетями Заключение Список основных источников

3 Введение Предложенная А.Тихомировым (Московский государственный университет имени М.В.Ломоносова, РФ), А.Труфановым (Иркутский государственный технический университет, РФ) и др. концепция кружева единых сетей КЕС (или ART2 кружево), базируется на сквозном описании основных категорий взаимодействия множества сущностей ( субъектов, объектов) с помощью многослойного ( многоуровневого ) набора сетей произвольной топологии, в т.ч. комплексных.

4 Введение (продолжение) В основе подхода лежат бинарные (парные) взаимодействия сущностей (акторов) в отдельных тематических слоях (ТС).

5 Введение (продолжение) Актором кружева единой сети является ствол, стволы крепят узлы сетей различных тематических слоев. Ствол вырождается в узел, а единая сеть в традиционную сеть при объединении всех ТС в один. КЕС -сеть представляет собой квинтет (кортеж, семейство) (S, T, V, Vt, Et), где S – непустое множество стволов, T – непустое множество тематических слоев, V – множество, называемое узлами сети, причем V представляет кортеж неотделимых непересекающихся непустых подмножеств множества V ((V1,… Vt), называемых узлами тематических слоев t КЕС-сети, Et– семейство непустых (необязательно различных) подмножеств множества Vt, называемых связями тематического слоя t CNL- сети.

6 Введение (продолжение) Авторами предлагается математическое описание частного случая КЕС, так называемой стволовой сети (stem network), s-сети задаваемой не квинтетом, а тройкой (S, T, R), где S – непустое множество стволов, T – непустое множество тематических слоев, R=(R 1, R 2, …, R t )– совокупность бинарных отношений на множестве S, где R i соответствует тематическому слою i. Множество узлов V можно исключить из описания, так как каждый узел является, по сути, пересечением ствола и тематического слоя.

7 В такой интерпретации s- сеть представляет собой совокупность графов, заданных на одном и том же множестве узлов. Каждый отдельный граф задает связи между узлами в тематическом слое. В теории графов одним из способов задания графа является матрица смежности. Учитывая многослойность рассматриваемой сети, матрица смежности может быть задана как трехмерная матрица вида, где Представление s-сетей

8 Пример трёхмерной кубической матрицы для трехслойной? s-сети. Представление s-сетей (продолжение)

9 Аналогичным способом можно задать матрицу весов связей, Представление s-сетей (продолжение)

10 Тогда очевидным образом для s-сети можно определить операции, аналогичные операциям над графами. Представление s-сетей (продолжение)

11 Операцией добавления к сети (S, T, R) ствола a образуется сеть Унарные операции Сеть (S, T, R) Операция добавления к сети (S, T, R) ствола a а

12 Операция добавления тематического слоя t к сети (S, T, R) состоит в образовании сети Унарные операции (продолжение) Сеть (S, T, R) Операция добавления тематического слоя t к сети (S, T, R)

13 Операция добавления дуги (а k, b k ) в тематический слой k к сети (S, T, R) состоит в образовании сети Унарные операции (продолжение) Сеть (S, T, R) Операция добавления дуги (а k, b k ) в тематический слой k

14 Операция удаления дуги (а k, b k ) из тематического слоя k сети (S, T, R) состоит в образовании сети (S, T, R=(R 1, R 2, …, R k \{(а k, b k )}, …, R t )). Унарные операции (продолжение) Сеть (S, T, R) Операция удаления дуги (а k, b k ) из тематического слоя k

15 Операция удаления ствола а из сети (S, T, R) заключается в удалении ствола а вместе с инцидентными ему дугами. (S\{a}, T, R={R k \{(b k, c k )| b k = a k или с k = a k, k=1,2,…,n, n-количество слоев}. Унарные операции (продолжение) Сеть (S, T, R) Операция удаления ствола а из сети (S, T, R) а

16 Операцией сечения сети (S, T, R) по тематическому слою k образуется граф (S, R k ). Унарные операции (продолжение) Сеть (S, T, R) Операцией сечения сети (S, T, R) по тематическому слою k

17 Операция удаления тематического слоя t из сети (S, T, R) состоит в образовании сети (S, T \ t k, R\ R k ). Унарные операции (продолжение) Сеть (S, T, R) Операция удаления тематического слоя t из сети (S, T, R)

18 Операция отождествления стволов a и b сети (S, T, R) состоит в удалении из сети (S, T, R) стволов a и b и присоединении нового ствола а', дуг (а',с), если (а,с) R k или (b,с) R k, и дуг (с,a'), если (с, а) R k или (с, b) R k. Если в каком–либо слое стволы соединены дугой, операция отождествления стволов подразумевает удаление этой дуги, т.к. рассматриваемые нами конструкции не имеют петель. Унарные операции (продолжение)

19 Сеть (S, T, R)Операция отождествления стволов a и b сети (S, T, R)) а b a

20 Операция дополнения слоя. Дополнением слоя t k называется граф (S, t k, S 2 \(R k {(а i, a i )|a i t k })). В результате применения этой операции к сети (S, T, R) получаем сеть (S, T, R=(R 1,…,R k-1,S 2 \(R k {(а i, a i )|a i t k }, R k+1,…,R t )). Операции над слоями Дополнение слоя

21 Операция объединения слоев. Объединением слоев t i и t j называется граф (S, R i R j ) В результате применения этой операции к сети (S, T, R) получаем сеть (S, T, R=(R 1,…,R k-1,R k =R k R k+1, R k+2,…,R t )). Операции над слоями (продолжение) Объединение слоев

22 Операция пересечения слоев. Пересечением слоев t i и t j называется граф (S, R i R j ) В результате применения этой операции к сети (S, T, R) получаем сеть (S, T, R=(R 1,…,R k-1,R k =R k R k+1, R k+2,…,R t )). Операции над слоями (продолжение) Пересечение слоев

23 Кольцевая сумма слоев. Кольцевой суммой слоев t i и t j называется граф (S, R i R j ) В результате применения этой операции к сети (S, T, R) получаем сеть (S, T, R=(R 1,…,R k-1,R k =(R k \R k+1 ) (R k+1 \R k ), R k+2,…,R t )). Операции над слоями (продолжение) Кольцевая сумма слоев

24 Операция дополнения сети. Дополнением сети (S, T, R) называется сеть (S, T, S 2 \ R ). Бинарные операции над сетями Операция дополнения сети

25 Операция объединения сетей. Объединением сетей (S 1, T 1, R 1 ) и (S 2, T 2, R 2 ) называется сеть (S 1 S 2, T 1 T 2, R 1 R 2 ). Бинарные операции над сетями (продолжение) Операция объединения сетей

26 Операция пересечения сетей. Пересечением сетей (S 1, T 1, R 1 ) и (S 2, T 2, R 2 ) называется сеть (S 1 S 2, T 1T 2, R 1 R 2 ). Бинарные операции над сетями (продолжение) Операция пересечения сетей

27 Кольцевая сумма сетей. Кольцевой сетей (S 1, T 1, R 1 ) и (S 2, T 2, R 2 ) называется сеть (S 1 S 2, T 1 T 2, R 1 R 2 = (R 1 \ R 2 ) (R 2 \ R 1 )). Бинарные операции над сетями (продолжение) Кольцевая сумма сетей

28 Благодаря введению s-сетей, и рассмотренным на них операциям можно формализовать многие прикладные задачи в различных областях знаний. Особенно удачно и значимо приложение этой теории к экономической и социальной сферам. При этом каждая введенная операция имеет свое содержательное отображение на реальных технологических, экономических и биосоциальных сетях. Заключение

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

30 A.А.Тихомиров, А.И.Труфанов. Сверхсложные сети: новые модели интерпретации социально-экономических и биосоциальных процессов. Труды Института государства и права РАН. - М.: ИГП РАН, 6, с (дата обращения: ). S. H. Strogatz, Exploring Complex Networks, Nature V. 410, 2001, с R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 2002 с.47 M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45, 2003, с О. Оре. Теория графов. – Либроком г Список основных источников