Système dynamique graphique - Graph dynamical system

En mathématiques , le concept de systèmes dynamiques de graphes peut être utilisé pour capturer un large éventail de processus se déroulant sur des graphes ou des réseaux. Un thème majeur de l'analyse mathématique et computationnelle des GDS est de relier leurs propriétés structurelles (par exemple, la connectivité du réseau) et la dynamique globale qui en résulte.

Le travail sur les GDS considère les graphes finis et les espaces d'états finis. En tant que tel, la recherche implique généralement des techniques provenant, par exemple, de la théorie des graphes , de la combinatoire , de l' algèbre et des systèmes dynamiques plutôt que de la géométrie différentielle. En principe, on pourrait définir et étudier les GDS sur un graphe infini (par exemple, des automates cellulaires ou des automates cellulaires probabilistes sur ou des systèmes de particules en interaction quand un certain caractère aléatoire est inclus), ainsi que des GDS avec un espace d'états infini (par exemple dans les réseaux de cartes couplées); voir, par exemple, Wu. Dans ce qui suit, tout est implicitement supposé être fini, sauf indication contraire.

Définition formelle

Un système graphique dynamique est construit à partir des composants suivants:

  • Un graphe fini Y avec un ensemble de sommets v [ Y ] = {1,2, ..., n}. En fonction du contexte, le graphique peut être dirigé ou non.
  • Un état x v pour chaque sommet v de Y pris à partir d' un ensemble fini K . L' état du système est le n -tuple x = ( x 1 , x 2 , ..., x n ), et x [ v ] est le tuple constitué des états associés aux sommets dans le 1-voisinage de v dans Y (dans un ordre fixe).
  • Une fonction de sommet f v pour chaque sommet v . La fonction de sommet cartes de l'état de sommet v à l' instant t à l'état de sommet à l' instant t  + 1 sur la base des états associés à la 1-voisinage de v dans Y .
  • Un schéma de mise à jour spécifiant le mécanisme par lequel la cartographie des états de sommets individuels est effectuée de manière à induire un système dynamique discret avec l'application F : K n → K n .

L' espace des phases associé à un système dynamique avec l'application F : K n → K n est le graphe orienté fini avec l'ensemble de sommets K n et les arêtes dirigées ( x , F ( x )). La structure de l'espace des phases est régie par les propriétés du graphe Y , les fonctions de sommet ( f i ) i et le schéma de mise à jour. La recherche dans ce domaine vise à déduire les propriétés de l'espace des phases basées sur la structure des constituants du système. L'analyse a un caractère local à global.

Automates cellulaires généralisés (GCA)

Si, par exemple, le schéma de mise à jour consiste à appliquer les fonctions de sommet de manière synchrone, on obtient la classe des automates cellulaires généralisés (CA). Dans ce cas, l'application globale F : K n → K n est donnée par

Cette classe est appelée automates cellulaires généralisée depuis les classiques ou standards automates cellulaires sont généralement définis et étudiés sur des graphiques réguliers ou des grilles, et les fonctions de vertex sont généralement supposée être identiques.

Exemple: Soit Y le graphe circulaire sur les sommets {1,2,3,4} d'arêtes {1,2}, {2,3}, {3,4} et {1,4}, noté Circ 4 . Soit K = {0,1} l'espace d'états pour chaque sommet et utilise la fonction ni 3  : K 3 → K défini par ni 3 ( x, y, z ) = (1 +  x ) (1 +  y ) (1 +  z ) avec module arithmétique 2 pour toutes les fonctions de sommet. Ensuite, par exemple, l'état du système (0,1,0,0) est mappé sur (0, 0, 0, 1) à l'aide d'une mise à jour synchrone. Toutes les transitions sont affichées dans l'espace des phases ci-dessous.

326

Systèmes dynamiques séquentiels (SDS)

Si les fonctions de sommet sont appliquées de manière asynchrone dans la séquence spécifiée par un mot w = ( w 1 , w 2 , ..., w m ) ou permutation = ( , ) de v [ Y ] on obtient la classe des systèmes dynamiques séquentiels ( SDS). Dans ce cas, il est commode d'introduire les cartes Y- locales F i construites à partir des fonctions de sommet par

La carte SDS F = [ F Y , w ]: K n → K n est la composition de la fonction

Si la séquence de mise à jour est une permutation on parle fréquemment d'une permutation SDS pour souligner ce point.

Exemple: Soit Y le graphe circulaire sur les sommets {1,2,3,4} d'arêtes {1,2}, {2,3}, {3,4} et {1,4}, noté Circ 4 . Soit K = {0,1} l'espace d'états pour chaque sommet et utilise la fonction ni 3  : K 3 → K défini par ni 3 ( x, y, z ) = (1 +  x ) (1 +  y ) (1 +  z ) avec module arithmétique 2 pour toutes les fonctions de sommet. En utilisant la séquence de mise à jour (1, 2, 3, 4), l'état du système (0, 1, 0, 0) est mappé sur (0, 0, 1, 0). Toutes les transitions d'état du système pour ce système dynamique séquentiel sont affichées dans l'espace de phase ci-dessous.

326

Systèmes dynamiques de graphes stochastiques

Du point de vue des applications, par exemple, il est intéressant de considérer le cas où un ou plusieurs des composants d'un GDS contiennent des éléments stochastiques. Les applications motivantes pourraient inclure des processus qui ne sont pas entièrement compris (par exemple, la dynamique à l'intérieur d'une cellule) et où certains aspects à toutes fins pratiques semblent se comporter selon une distribution de probabilité. Il existe également des applications régies par des principes déterministes dont la description est si complexe ou si peu maniable qu'il est logique de considérer des approximations probabilistes.

Chaque élément d'un système dynamique graphique peut être rendu stochastique de plusieurs manières. Par exemple, dans un système dynamique séquentiel, la séquence de mise à jour peut être rendue stochastique. A chaque étape d'itération, on peut choisir la séquence de mise à jour w au hasard à partir d'une distribution donnée de séquences de mise à jour avec des probabilités correspondantes. L'espace de probabilité correspondant des séquences de mise à jour induit un espace de probabilité des cartes SDS. Un objet naturel à étudier à cet égard est la chaîne de Markov sur l'espace d'états induite par cette collection de cartes SDS. Ce cas est appelé séquence de mise à jour GDS stochastique et est motivé, par exemple, par des processus où des "événements" se produisent au hasard selon certains taux (par exemple des réactions chimiques), la synchronisation dans des simulations de calcul parallèle / d'événements discrets et dans des paradigmes de calcul décrits plus loin .

Cet exemple spécifique avec séquence de mise à jour stochastique illustre deux faits généraux pour de tels systèmes: lors du passage à un système dynamique de graphe stochastique on est généralement conduit à (1) une étude des chaînes de Markov (avec une structure spécifique régie par les constituants du GDS), et (2) les chaînes de Markov résultantes ont tendance à être grandes avec un nombre exponentiel d'états. Un objectif central de l'étude du GDS stochastique est de pouvoir dériver des modèles réduits.

On peut également considérer le cas où les fonctions de sommet sont stochastiques, c'est-à-dire la fonction stochastique GDS . Par exemple, les réseaux booléens aléatoires sont des exemples de fonction GDS stochastique utilisant un schéma de mise à jour synchrone et où l'espace d'états est K = {0, 1}. Les automates cellulaires probabilistes finis (ACP) sont un autre exemple de fonction GDS stochastique. En principe, la classe des systèmes de particules en interaction (IPS) couvre l' ACP finie et infinie , mais en pratique le travail sur IPS est largement concerné par le cas infini puisque cela permet d'introduire des topologies plus intéressantes sur l'espace d'états.

Applications

Les systèmes dynamiques graphiques constituent un cadre naturel pour capturer des systèmes distribués tels que les réseaux biologiques et les épidémies sur les réseaux sociaux, dont beaucoup sont souvent appelés systèmes complexes.

Voir également

Les références

Lectures complémentaires

Liens externes