Introduction aux Graphes d’Interaction

Depuis 1999, date à laquelle sont apparus les systèmes pair-à-pair (réseaux sociaux, la messagerie instantanée ou le Chat, systèmes de partage de fichiers, etc.). Les systèmes P2P n’ont cessé de croître au point d’être aujourd’hui estimés à plusieurs dizaines de millions d’utilisateurs. Les réseaux pair-à-pair ne sont pas les seuls réseaux de cette importance, on rencontre dans différents domaines des réseaux d’interactions de très grande taille.

On appelle réseau d’interactions tout ensemble d’entités interagissant de façon individuelle. Les grands réseaux d’interactions recouvrent ainsi des réseaux aussi divers que le réseau des routeurs d’Internet, le réseau des contacts sociaux entre individus, ou le réseau des réactions chimiques entre protéines dans le métabolisme d’un être vivant. On parle également de réseaux réels. Des études récentes ont montré qu’en modélisant ces réseaux par des graphes, on observait des propriétés communes malgré leurs origines diverses (Internet, Web, Sociologie, Chimie, …etc.). La connaissance des propriétés des réseaux d’interactions est nécessaire afin de prévoir leur évolution et de déterminer leurs capacités à résister à différents phénomènes ou tout simplement de comprendre leur nature.

La modélisation de réseaux d’interactions consiste à construire des graphes aléatoires avec les mêmes propriétés que les réseaux réels. L’intérêt est de pouvoir effectuer sur machines des simulations de propagation, de pannes, d’attaque et d’autres événements qui peuvent survenir sur les réseaux réels. L’avantage de la modélisation est de pouvoir obtenir des graphes de grande taille ayant des propriétés réelles en temps raisonnable.

Définition d’un graphe d’interaction

Les graphes d’interaction sont une modélisation utilisée dans de nombreuses disciplines. A un instant de l’évolution du réseau, les acteurs sont les nœuds d’un graphe où une arête (arc) modélisent une interaction entre les deux nœuds qu’elle relie. Ce réseau est bien sûr dynamique, des nœuds peuvent être ajoutés ou supprimés durant son évolution. Les arêtes peuvent aussi être dynamiques selon la définition de l’interaction considérée [1].

Une interaction, dans un tel réseau, est définie selon ce que l’on cherche à modéliser, par exemple :
➤ Les réseaux issus de l’Internet : Un des réseaux les plus connu est le réseau Internet (ou encore les réseaux d’Internet). Plusieurs applications utilisent ce réseau pour transmettre de l’information, tel que « World-Wide-Web » ou encore « pair-à-pair ». Les instances de ces applications sont représentées par des nœuds, et les relations qu’elles entretiennent entre elles, peuvent être vues comme des arêtes.

➤ Les réseaux sociaux : Les graphes d’interactions sont utilisés couramment en sciences sociales pour modéliser des interactions entre individus. Les sommets représentent alors les entités ou individus, et les arêtes ou arcs une relation ou interaction entre eux.

➤ Les réseaux de cooccurrence lexicale : Le graphe de cooccurrence lexicale d’un document donné est un graphe dont les sommets sont des mots d’un document. Deux mots sont reliés s’ils apparaissent proches dans le document [2].

Propriétés communes des réseaux d’interactions

Petit diamètre et distance moyenne faible

Le diamètre d’un graphe est le plus long des chemins parmi l’ensemble des plus courts chemins pour tout couple de nœuds dans le graphe. La distance moyenne est la moyenne des longueurs des plus courts chemins entre tous les couples de nœuds d’un graphe. Beaucoup ont pensé que le diamètre des réseaux d’interactions pourrait être grand et que leur distance moyenne pourrait être forte. Mais des études dans [5, 6, 7] sur différents réseaux d’interactions ont montré qu’il n’en est rien.

Les réseaux d’interactions ont un petit diamètre et une distance moyenne faible de l’ordre de log(n) où n est la taille du graphe. Le calcul de la distance moyenne et du diamètre étant coûteux en temps, une estimation de la distance moyenne est faite en l’évaluant seulement pour un certain nombre de paires de sommets.

Modélisation des réseaux d’interactions 

L’étude des grands graphes d’interaction a permis de découvrir les principales propriétés de ces graphes. De nombreux scientifiques ont dès lors cherché à trouver un modèle qui se rapprocherait le plus des grands réseaux réels. Historiquement, ce genre de graphe ont été d’abord assimilés à des graphes aléatoires mais de nombreuses différences subsistent.

Dans les points qui suivent nous allons tenter de présenter les principaux modèles proposés ainsi que les points de similarités et de divergences avec les réseaux réels.

Les Graphes aléatoires uniformes

Rien, à priori, ne relie les différents graphes réalistes. Ce qui amène à penser tout simplement que ces graphes ne sont que le résultat d’interconnexions établies au hasard entre les nœuds. La théorie des graphes aléatoires a été introduite par Paul Erdös et Alfred Rényi après la découverte d’Edrös qui démontre que des méthodes probabilistes peuvent être très utiles pour venir à bout de certains problèmes dans la théorie des graphes. La modélisation des grands réseaux d’interaction par des graphes aléatoires était donc une première tentative. Elle était considérée, jusqu’à récemment, comme la seule méthode, par défaut, pour les réseaux réels.

Le modèle aléatoire d’Erdös et Rényi
Lors d’une série de séminaires entre 1950 et 1960, Paul Erdös et Alfréd Rényi ont proposé et étudié les premiers modèles de réseaux d’interactions appelés les graphes aléatoires . Erdös et Rényi ont apporté plusieurs versions de ce modèle, le plus étudié est construit comme suit :
1- Ajouter n sommets.
2- Pour tout couple de sommets, une arête est ajoutée avec une probabilité p.

Bilan de ce modèle :
Les récentes observations expérimentales (qui étaient impossibles ou très partielles auparavant) ont mis en lumière d’importantes différences. Ainsi, la distribution des degrés dans les graphes aléatoire d’Erdös et Rényi suit une loi de Poisson (exponentielle) alors qu’il s’agit d’une loi de puissance pour la grande majorité des réseaux réels. Ce graphe a un faible coefficient de clustering puisque les voisins d’un nœud n’ont aucune raison d’être davantage reliés entre eux que deux nœuds pris au hasard. Néanmoins, les graphes d’Erdös et Rényi partagent la caractéristique du petit diamètre avec les réseaux réels.

Les graphes petit-monde

Les graphes petit monde (Small World) sont nés après l’apparition du concept des « six degrés de séparation ». Le concept des six degrés de séparation a été imaginé par le Hongrois Frigyes Karinthy en 1929. Cette idée théorique évoque la possibilité que toute personne sur le globe peut être reliée à n’importe quelle autre à travers une chaîne de relations individuelles comprenant au plus cinq autres maillons.

Cette théorie fut reprise en 1967 par le psycho-sociologue Stanley Milgram qui a réalisé une série d’expériences dont le résultat est connu sous le nom de «six degrés de séparation». La conclusion de ses études est, que deux personnes quelconques dans le monde ont une chaîne de connaissances de longueur six en moyenne. En d’autres termes, il y a cinq personnes intermédiaires qui séparent les deux personnes étrangères l’une de l’autre. Par contre, après plus de trente ans, le statut de cette idée comme description de réseaux sociaux hétérogènes reste une question ouverte. Des études sont encore menées actuellement sur le « petit monde ».