Les Réseaux Complexes, du Rà Modélisation

Problématique : modélisation d’un réseau complexe

Dans les réseaux réels, alors que les interactions locales sont généralement bien connues (la communication entre deux routeurs, la réaction entre deux protéines), le résultat global de l’ensemble des interactions est encore mal compris (propriété d’émergence) [45].

La compréhension de ces propriétés globales touche pourtant à des problématiques essentielles : la dynamique des interactions dans un réseau social ou un réseau informatique est par exemple liée à la problématique de la propagation des virus (informatiques ou biologiques), celle d’un réseau de distribution d’électricité, au problème de la robustesse d’un grand réseau. L’augmentation récente des capacités de traitement et de collecte d’un grand nombre de données statistiques sur ces réseaux a permis l’essor des études de ces objets. En particulier, on a observé expérimentalement que ces réseaux, a priori éloignés, partageaient des propriétés macroscopiques communes [79]. Le problème majeur réside dans la modélisation de tels réseaux. Or, pour pouvoir créer des modèles cohérents et reflétant au maximum les propriétés des réseaux réels, il  s faut être en mesure de les caractériser. C’est seulement en réussissant à caractériser tel ou tel réseau que l’on pourra reproduire leur comportement lors de simulations. Pour le moment, ces simulations donnent certains résultats mais ceux-ci ne sont pas toujours très pertinents ou ne prennent pas en compte tous les facteurs d’intéractions nécessaires [71].

La caractérisation de l’anatomie d’un réseau fait référence à des définitions incomplètes, d’o`u le besoin de rechercher une (ou plusieurs) définition(s) générale(s) permettant la reconnaissance et/ou la construction d’un réseau complexe.

La théorie des graphes

Pour représenter les réseaux, la théorie des graphes paraˆıt l’outil adéquat. C’est principalement cet outil qui a été utilisé dans les différentes études qui ont porté sur la modélisation de réseaux complexes. Dans cette partie, la théorie des graphes sera présentée, puis on étudiera les caractéristiques des propriétés structurelles d’un graphe pour arriver au problème de la dynamique, ainsi que les limites des études auxquelles on se confronte à l’heure actuelle.

Définition et concepts de base

La théorie des graphes est née en 1736 quand Euler démontra qu’il était impossible de traverser chacun des sept ponts de la ville russe de K¨onigsberg (aujourd’hui Kaliningrad) une fois exactement et de revenir au point de départ. Les ponts enjambent les bras de la Pregel qui coulent de part et d’autre de l’ˆıle de Kneiphof. Sur la figure 1.2, les noeuds représentent les rives. Fig. 1.2 – Ponts de K¨onigsberg La théorie des graphes constitue un domaine des mathématiques qui, historiquement, s’est aussi développé au sein de disciplines diverses telles que la chimie (modélisation de structures), la biologie (génome), les sciences sociales (modélisation des relations) ou en vue d’applications industrielles (problème du voyageur de commerce). Elle constitue l’un s des instruments les plus courants et les plus efficaces pour résoudre des problèmes discrets posés en Recherche Opérationnelle (RO).

De manière générale, un graphe permet de représenter simplement la structure, les connexions, les cheminements possibles d’un ensemble complexe comprenant un grand nombre de situations, en exprimant les relations, les dépendances entre ses éléments (e.g., réseau de communication, réseaux ferroviaire ou routier, arbre généalogique, diagramme de succession de tˆaches en gestion de projet, …). En plus de son existence purement mathématique, le graphe est aussi une structure de données puissante pour l’informatique [61]. Concepts orientés Dans beaucoup d’applications, les relations entre éléments d’un ensemble sont orientées, i.e., un élément x peut être en relation avec un autre y sans que y soit nécessairement en relation avec x.

On parle alors de graphe orienté (en Anglais directed graph ou plus simplement digraph). Définition 1.1 Un graphe G = (X, U) est déterminé par : – un ensemble X = {x1, x2, …, xn} dont les éléments sont appelés sommets ou noeuds (ce dernier terme est plutˆot utilisé dans le contexte des réseaux). – un ensemble U = {u1, u2, …, um} du produit cartésien X × X dont les éléments sont appelés arcs. Pour un arc u = (xi , xj ), xi est l’extrémité initiale, xj l’extrémité finale (ou bien origine et destination). L’arc u part de xi et arrive à xj . Un arc (xi , xi) est appelé une boucle. Un p−graphe est un graphe dans lequel il n’existe jamais plus de p arcs de la forme (i, j) entre deux sommets quelconques. On appellera communément « graphe »un 1 − graphe. La densité d’un graphe est donnée par le quotient m/n2 , rapport du nombre effectif d’arcs sur le nombre maximal théorique.