Графическая динамическая система

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

В работе над GDS рассматриваются конечные графы и пространства с конечными состояниями. Таким образом, исследование обычно включает в себя методы, например, из теории графов , комбинаторики , алгебры и динамических систем, а не из дифференциальной геометрии. В принципе, можно было бы определить и изучить ГДА над бесконечным графом (например , клеточные автоматы или вероятностные клеточные автоматы над или системами взаимодействующих частиц , когда некоторые случайности включены), а также ГДА с бесконечным пространством состояний (например , как в решетках связанных отображений); см., например, Wu. ^[1]${\ displaystyle \ mathbb {Z} ^ {k}}$${\ Displaystyle \ mathbb {R}}$ В дальнейшем все неявно предполагается конечным, если не указано иное.

Формальное определение [ править ]

Графическая динамическая система состоит из следующих компонентов:

• Конечный граф Y с множеством вершин v [ Y ] = {1,2, ..., n}. В зависимости от контекста граф может быть направленным или неориентированным.
• Состояние х _v для каждой вершины V из Y , взятый из конечного множества K . Состояние системы - это n -набор x = ( x ₁ , x ₂ , ..., x _n ), а x [ v ] - набор, состоящий из состояний, связанных с вершинами в 1-окрестности v в Y (в фиксированном порядке).
• Вершинная функция F _v для каждой вершины V . Вершинная функция отображает состояние вершины V в момент времени т в состояние вершины в момент времени т  + 1 на основе состояний , связанных с 1-окрестности V в Y .
• Схема обновления, определяющая механизм, с помощью которого выполняется отображение состояний отдельных вершин, чтобы вызвать дискретную динамическую систему с отображением F : K ⁿ → K ⁿ .

Фазовое пространство , связанное с динамической системой с картой F : К ^п → К ^п есть конечный ориентированный граф с множеством вершин К ^п и направленные ребра ( х , Р ( х )). Структура фазового пространства определяется свойствами графа Y , вершинными функциями ( f _i ) _i и схемой обновления. Исследования в этой области направлены на определение свойств фазового пространства на основе структуры компонентов системы. Анализ носит локальный и глобальный характер.

Обобщенные клеточные автоматы (GCA) [ править ]

Если, например, схема обновления состоит из синхронного применения вершинных функций, получается класс обобщенных клеточных автоматов (КА). В этом случае глобальное отображение F : K ⁿ → K ⁿ имеет вид

${\ Displaystyle F (x) _ {v} = f_ {v} (x [v]) \ ;.}$

Этот класс называется обобщенными клеточными автоматами, поскольку классические или стандартные клеточные автоматы обычно определяются и изучаются на регулярных графах или сетках, а вершинные функции обычно считаются идентичными.

Пример: Пусть Y - круговой граф на вершинах {1,2,3,4} с ребрами {1,2}, {2,3}, {3,4} и {1,4}, обозначенный Circ ₄ . Пусть K = {0,1} будет пространством состояний для каждой вершины и использовать функцию nor ₃  : K ³ → K, определенную формулой nor ₃ ( x, y, z ) = (1 +  x ) (1 +  y ) (1 +  z ) с арифметикой по модулю 2 для всех вершинных функций. Затем, например, состояние системы (0,1,0,0) отображается в (0, 0, 0, 1) с использованием синхронного обновления. Все переходы показаны в фазовом пространстве ниже.

326

Последовательные динамические системы (SDS) [ править ]

Если вершинные функции применяются асинхронно в последовательности, заданной словом w = ( w ₁ , w ₂ , ..., w _m ) или перестановкой = ( , ) из v [ Y ], получается класс последовательных динамических систем ( SDS). ^[2] В этом случае удобно ввести Y -локальные отображения F _i, построенные из вершинных функций формулой${\ displaystyle \ pi}$${\ displaystyle \ pi _ {1}}$${\ displaystyle \ pi _ {2}, \ dots, \ pi _ {n}}$

${\ Displaystyle F_ {i} (x) = (x_ {1}, x_ {2}, \ ldots, x_ {i-1}, f_ {i} (x [i]), x_ {i + 1}, \ ldots, x_ {n}) \ ;.}$

SDS-карта F = [ F _Y , w ]: K ⁿ → K ⁿ - это композиция функций

${\ displaystyle [F_ {Y}, w] = F_ {w (m)} \ circ F_ {w (m-1)} \ circ \ cdots \ circ F_ {w (2)} \ circ F_ {w (1 )} \ ;.}$

Если последовательность обновления представляет собой перестановку, часто говорят о SDS перестановки, чтобы подчеркнуть этот момент.

Пример: Пусть Y - круговой граф на вершинах {1,2,3,4} с ребрами {1,2}, {2,3}, {3,4} и {1,4}, обозначенный Circ ₄ . Пусть K = {0,1} будет пространством состояний для каждой вершины и использовать функцию nor ₃  : K ³ → K, определенную формулой nor ₃ ( x, y, z ) = (1 +  x ) (1 +  y ) (1 +  z ) с арифметикой по модулю 2 для всех вершинных функций. Используя последовательность обновления (1,2,3,4), состояние системы (0, 1, 0, 0) отображается в (0, 0, 1, 0). Все переходы состояний системы для этой последовательной динамической системы показаны в фазовом пространстве ниже.

326

Стохастические графические динамические системы [ править ]

Например, с точки зрения приложений интересно рассмотреть случай, когда один или несколько компонентов GDS содержат стохастические элементы. Мотивационные приложения могут включать в себя процессы, которые не до конца поняты (например, динамика внутри ячейки), и где определенные аспекты для всех практических целей, кажется, ведут себя в соответствии с некоторым распределением вероятностей. Существуют также приложения, основанные на детерминированных принципах, описание которых настолько сложно или громоздко, что имеет смысл рассматривать вероятностные приближения.

Каждый элемент графической динамической системы можно сделать стохастическим несколькими способами. Например, в последовательной динамической системе последовательность обновления может быть сделана стохастической. На каждом шаге итерации можно выбрать последовательность обновления w случайным образом из заданного распределения последовательностей обновления с соответствующими вероятностями. Соответствующее вероятностное пространство обновленных последовательностей индуцирует вероятностное пространство SDS-карт. Естественным объектом для изучения в этом отношении является цепь Маркова на пространстве состояний, индуцированная этим набором SDS-отображений. Этот случай называется стохастической GDS последовательности обновления. и мотивируется, например, процессами, в которых «события» происходят случайным образом в соответствии с определенными скоростями (например, химические реакции), синхронизацией в параллельных вычислениях / симуляциях дискретных событий и в вычислительных парадигмах, описанных ниже.

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

Можно также рассмотреть случай, когда вершинные функции являются стохастическими, т.е. функция стохастическая GDS . Например, случайные булевы сети являются примерами стохастической GDS функций, использующей схему синхронного обновления и где пространство состояний равно K = {0, 1}. Конечные вероятностные клеточные автоматы (PCA) - еще один пример функции стохастической GDS. В принципе, класс систем взаимодействующих частиц (IPS) охватывает конечные и бесконечные PCA , но на практике работа над IPS в основном связана с бесконечным случаем, поскольку это позволяет вводить более интересные топологии в пространстве состояний.

Приложения [ править ]

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

См. Также [ править ]

• Теория сети химических реакций
• Динамический сетевой анализ ( тема социальных наук )
• Конечные автоматы
• Сети Хопфилда
• Сети Кауфмана
• Сети Петри

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Маколей, Мэтью; Мортвейт, Хеннинг С. (2009). «Циклическая эквивалентность графических динамических систем». Нелинейность . 22 (2): 421–436. arXiv : 0802.4412 . Bibcode : 2009Nonli..22..421M . DOI : 10.1088 / 0951-7715 / 22/2/010 .
• Голубицкий, Мартин ; Стюарт, Ян (2003). Перспектива симметрии . Базель: Биркхаузер. ISBN 0-8176-2171-7. CS1 maint: обескураженный параметр ( ссылка )

Внешние ссылки [ править ]

• Графические динамические системы - математическая основа для систем, основанных на взаимодействии, их анализ и моделирование, Хеннинг Мортвейт