Les graphes et les grands réseaux complexes : l’approche moderne

Les réseaux et les graphes sont une même chose. Les graphes sont étudiés par les mathématiciens depuis longtemps, depuis au moins 200 ans ou même peut‑être pas loin de 300 ans.

Mais les graphes étudiés par les mathématiciens, sont petits et de dimensions bornées (i.e. avec des limites).

Les graphes que l’on retrouve dans le monde qui nous entoure, comme ceux qui peuvent servir de représentation formelle pour la propagation des maladies, des rumeurs, ou les réseaux informatiques à grandes échelles, ne sont étudiés que depuis peu, depuis environ entre 1998 et 2000, et même encore plutôt après.

Cet exposé de Marc Barthélemy, docteur en physique théorique, nous parle de l’approche moderne de la théorie des graphes et des réseaux. Il aborde aussi la question de l’approche concrète de ces structures, avec l’étude et les mesures faites sur des cas réels — des approches qui n’étaient pas possibles jusque récemment (début du XXI‑ième siècle).

Il parle de la découverte d’une catégorie de graphe qui n’était pas soupçonnée avant les années 2000 : les graphes sans échelles. Ce sont des graphes hétérogènes, dans lesquelles il n’existe pas de connectivité moyenne qui soit pertinente. Ces graphes sont également appelés des graphes complexes.

Des exemples de tels graphes sont les réseaux sociaux sur le Net, le Net lui‑même, les réseaux de transports aérien…

Il parle d’une expérience de Milgram, autre que celle qui lui est connue et dont il a été question sur le forum : une autre expérience où cette fois il demandait à des gens de transmettre une lettre à une personne inconnue, éventuellement en utilisant d’autres gens comme intermédiaires, et en comptant le nombre d’étapes utilisées en moyenne. Il a ainsi déterminé que dans les États‑Unis de son époque (qui comptaient déjà des millions d’habitants), n’importe quelle personne pouvait être jointe depuis n’importe quelle autre personne, en seulement 6 étapes en moyenne. Ce nombre étonnamment réduit d’étapes, a donné à ce type de graphe de relations, le nom de “small world”, c’est‑à‑dire « petit monde », même si ces graphes peuvent être constitués de millions de nœuds.

Il y a des problèmes de son dans la vidéo. À deux ou trois moments le son disparait; ce n’est pas votre ordi’, c’est la vidéo qui a été mal faite.

Réseaux complexes : d’internet aux pandémies — Marc Barthélemy — Festival de Fleurance

Sujet vraiment ardu mais passionnant !

.

Il faudra que je le re‑écoute pour noter les mesures qu’il considère comme pertinentes pour caractériser les graphes. Parce que même pour les graphes qu’il dit être sans échelles, il parle quand‑même de répartition des types de nœuds, ce qui est finalement une caractérisation tout de même.

En fait, c’est tout le festival dont est issu cet exposé qui est passionnant. Il y aurait de quoi faire un sujet pour chacun.