Penseur

jeudi, novembre 16, 2006

Réseaux

Via Aeiou, l’incontournable blog de Flu, je suis tombé sur le projet Visual Complexity, qui illustre à merveille les propriétés des réseaux. Je ne sais pas pour vous, mais j’ai toujours été épaté[1] que des domaines aussi différents que la biologie, l’informatique, ou la sociologie, utilisent le même outil, et produisent des dessins (on dit des graphes, en fait, pour représenter les réseaux) qui se ressemblent. Je vous invite à explorer ce projet et à dénicher les perles rares, comme cette fantastique simulation de l’univers, qui sert d’illustration à l’article, ou cette carte de la blogosphère politique américaine.

Evidemment, la tentation est grande d’étudier ces objets de façon abstraite et mathématique, sans ce soucier de ce que la représentation recouvre réellement. L’idée est de trouver des lois, des principes, qui régissent leur organisation, et d’en déduire des applications dans le monde réel. Après tout, c’est sur cet aller-retour réel-abstraction-réel que fonctionne les mathématiques, non ?

Et justement, l’étude des réseaux abstraits, avec leurs listes de nœuds et de connections, permet de les classer, ou au moins une bonne partie de ceux que l’on trouve en informatique, en physique, en biologie ou en sociologie en deux grandes catégories :

- les réseaux aléatoires, où la probabilité que deux éléments pris au hasard soit connectés est toujours la même. Ces réseaux, comme le plan du métro, tendent à avoir un nombre de liens par nœud oscillant autour d’une valeur moyenne.

- Les réseaux invariants d’échelle, qui compte quelques nœuds liés à un nombre énorme d’autres nœuds, et un grand nombre de nœuds faiblement connectés (à la limite, un seul lien vers un des nœuds principaux). Ils sont appelés invariants d’échelle car, pour des raisons statistiques, cette asymétrie très forte se retrouve quelque soit la taille de la portion du réseau (c’est-à-dire, quelle que soit son échelle) que l’on regarde. Internet, avec ses gros serveurs et ses millions d’utilisateurs qui leurs sont reliés, est l’exemple parfait de ce type de réseau.

Leurs propriétés sont très différentes, que ce soit le rythme de diffusion de l’information (ou de quoi que ce soit qui circule), ou la résistance à la coupure de liaisons ou à la destruction de nœuds. Internet a été conçu pour résister à de telles coupures, et effectivement, les réseaux invariants d’échelle résistent très bien à des attaques détruisant aléatoirement des nœuds. Là où un réseau aléatoire verrait rapidement des portions entières isolés du reste, un réseau invariant d’échelle peut continuer à faire circuler l’information d’un bout à l’autre même avec une proportion importante de sites touchés. Par contre, dès lors que les attaques sont ciblées sur les serveurs, le réseau invariant d’échelle s’effondre bien plus rapidement : c’est le principe de certaines attaques informatiques.

Je laisse le mot de la fin au site du CNRS :

Ainsi, de l'étude de l'infection des ordinateurs par un virus à la propagation de polluants dans l'environnement en passant par l'épidémiologie, la physique statistique n'a pas fini de percer les mystères des systèmes et phénomènes complexes. Pour qu'enfin, les réseaux ne soient plus inextricables.
Non, quand même, avant de partir : regardez ça, encore une fois. C'est tellement beau.


[1] Depuis un article sur les réseaux dans le hors-série de Pour la Science sur la complexité, en fait. En 2003, je crois bien.

3 commentaires:

Eric C. a dit…

Les réseaux de métros, et de voies ferrées ou de bus par extension, sont-ils vraiment considérés comme aléatoires, le but étant quand meme de minimiser la distance moyenne entre deux noeuds pris au hasard, donc a priori de "maximiser" le nombre de liens par noeud ?

Matthieu a dit…

ils ne sont évidement pas réellement aléatoires, ne serait-ce qu'a cause de la correlation entre les connections, cad les lignes de métro. Mais, tout de même, chaque station réalise avec ses plus proches voisins entre 2 et disons, 4 ou 5 liaisons. Vous n'avez pas, par exemple, chatelet qui est reliée à 30 stations, Nation et Montparnasse à 15, et le reste à une des trois précédentes.

Tom Roud a dit…

Hello,
pour compléter ton billet, il y a eu pas mal de travaux récemment de physiciens essayant notamment de caractériser les réseaux par rapport à leurs sous-modules (voir page web d'Uri Alon à Weizmann http://www.weizmann.ac.il/mcb/UriAlon/ , un des scientifiques les plus connus dans le domaine). Par exemple, dans un papier de Science ( R Milo, S Shen-Orr, S Itzkovitz, N Kashtan, D Chklovskii & U Alon,
Network Motifs: Simple Building Blocks of Complex Networks
Science, 298:824-827 (2002), disponible sur son site) il montre comment on peut caractériser un réseaux par ses sous-modules. Typiquement, même si la distribution a l'air aléatoire de loin (par exemple le réseau de bus), dans le détail, le réseau peut-être structuré (par exemple ton réseau de bus est purement linéaire, il n'y a quasiment pas d'arbres). C'est pareil pour les réseaux génétiques (où un réseau particulier est sur représenté), pour les réseaux de neurones...