463 - Des petits mondes dans les grandes lignes

N. Lygeros

Le concept de petit monde traduit le fait que dans la plupart des réseaux et ce indépendamment de la taille de ceux-ci, il existe un chemin relativement court entre deux noeuds quelconques. Cette constatation a été effectuée pour la première fois par la socio-psychologue Stanley Milgram en 1967. Elle a par la suite été étudiée de manière extensive de façon ponctuelle tout d’abord et plus systématique récemment. Bien que le concept de petit monde soit surprenant, il n’est pas pour autant révélateur d’une organisation donnée puisque Erdös et Rényi, dans le cadre de leur théorie sur les graphes aléatoires, ont montré que la distance entre deux noeuds quelconques était de l’ordre du logarithme de la taille du graphe aléatoire considéré.
Cependant les données empiriques que nous avons sur les réseaux complexes réels montrent que ces derniers appartiennent aux petits mondes. Aussi même s’ils ne sont pas caractéristiques, ils semblent génériques. C’est dans la lignée de cela que Goh et cie ont proposé une première classification des réseaux qui ont une invariance d’échelle et qui correspondent à l´évolution de l’étude dans le domaine des réseaux et des paradigmes. En effet les grandes classes de paradigmes sont les graphes aléatoires qui sont une variante du modèle d’Erdös-Rényi, les modèles des petits mondes qui sont des intermédiaires et enfin les modèles invariants d’échelle dont la distribution des degrés obéit à une loi de puissance. Cette dernière qui est plus spécifique permet d’exhiber des comportements universels.

La classification de Goh et cie comporte deux grandes classes. La première est relativement compacte tandis que la seconde est plutôt linéaire. Plus précisément la première classe correspond à des réseaux d’amas fortement connectés et la seconde classe à des réseaux dont la topologie est similaire à celle des arbres. Nous avons ainsi deux classes universelles de réseaux invariants d’échelle qui appartiennent aux petits mondes. Pour rendre compte des aspects dynamiques de la topologie de ces réseaux, Goh et cie se sont attachés à étudier leur résistance face à une attaque qui correspond concrêtement à l’élimination de certains noeuds et ils ont montré que la première classe était plus résistante que la seconde.

En réalité, une étude à partir des données empiriques était inutile puisque la théorie des graphes donne une bonne vision de ce résultat qui était donc prévisible et pour ainsi dire intuitif. Si nous considérons la première classe du point de vue topologique nous pouvons associer à chacun des amas d’un réseau donné de cette classe, un arbre de recouvrement minimal i.e. qui conserve la propriété de connexité. Aussi nous pouvons aisément visualiser une substructure qui correspond à la seconde classe. De même si nous considérons la seconde classe et que nous la complétons formellement par des liens redondants entre les noeuds, nous visualisons cette fois une superstructure qui correspond à la première classe. Ainsi via la minimalité ou la redondance ces classes apparaissent comme duales. Cette remarque justifie leur équi-universalité. De plus, via cette remarque, il est désormais évident que la première classe est plus résistante que la seconde puisqu’elle dispose d’un nombre beaucoup plus faible de sommets séparateurs du point de vue de la théorie des graphes. Ce qui confirme l’idée générale que la robustesse d’un système est directement liée à la redondance de sa structure. Aussi sans même encore parler de structure fractale de la géométrie des réseaux, il est prévisible que nous observerons une dominance de la première classe dans le domaine du vivant dans lequel la robustesse est un critère de sélection.