Dans cette unité, nous allons couvrir
un aspect différent de la structure des réseaux,
souvent appelée "structure d'échelle libre",
mais plus généralement "structure de réseau à longue queue".
Voici l'idée:
vous voyez l'image d'une structure typique
d'une partie du World Wide Web (WWW).
Les nœuds sont des pages web,
et les liens, des liens entre ces pages.
Vous pouvez voir qu'ils sont dirigés:
une page renvoie à une autre,
mais pas nécessairement l'inverse.
Vous pouvez aussi voir qu'il y a des hubs,
dans ce type de réseau, des pages qui renvoient
à beaucoup d'autres pages,
ainsi que des hubs vers lesquels
beaucoup de pages renvoient.
Comme ici.
Et, à l'inverse, nous avons un réseau aléatoire.
Voici à quoi cela peut ressembler,
si on lance une série de nœuds au hasard,
et que l'on place aléatoirement des liens entre eux.
Voyons la distribution de degré
dans ces différents types de réseaux.
Voici ce à quoi elle ressemble
dans un réseau aléatoire.
C'est un graphe sans numérotation,
mais vous pouvez voir sa forme,
cette courbe en forme de cloche,
qui est appelée une "distribution normale",
"distribution de Gauss",
ou, pour être vraiment exact, c'est aussi appelé
une "Distribution Poisson".
Mais le plus important, c'est la forme générale.
Ce qui est intéressant dans la distribution aléatoire,
c'est que la plupart des nœuds
ont le même nombre de liens.
Si on regarde ici au milieu, ce degré moyen,
est partagé par la plupart des nœuds.
Il y a un petit nombre de nœuds qui ont un bas degré,
et un autre petit nombre avec un haut degré,
et au-delà, on arrive vite à zéro.
On peut comparer cela
avec la distribution de degré du WWW.
Ici, vous avez une image de la distribution.
On y voit les mêmes barres, mais
elles sont tellement fines qu'on ne voit
qu'une masse toute noire.
Vous pouvez voir cela comme une sorte
de graphe en barres très compactes.
Les deux distributions sont très différentes l'une de l'autre.
Il y a un très grand nombre de nœuds avec un faible degré,
et un très petit nombre avec un degré élevé.
Il y a aussi un autre aspect intéressant.
Si je définis une échelle de 1000 à 10.000,
et que je prends ce petit carré,
qui commence à 10.000,
et que je me concentre dessus jusqu'à 100.000,
tout en gardant la même proportion:
l'axe va maintenant de 10.000 à 100.000,
j'ai zoomé sur la courbe.
Avant, on ne voyait que cette petite partie,
qui est devenue plus large,
même s'il y a maintenant un plus petit nombre de nœuds.
Je voudrais que vous vous concentriez
sur la forme:
si on zoome sur une petite partie,
la forme reste la même.
Si je coupais à 100.000 et que je regardais jusqu'à 1.000.000,
la forme resterait la même.
Cela doit vous faire penser aux fractales,
rappelez-vous que si vous en prenez une petite partie
et que vous l'examinez en détail,
elle ressemble à l'objet original entier.
C'est autosimilaire, à tous les niveaux.
Et une distribution sur loi de puissance est
un objet fractal,
comme nous l'avons vu
dans les chou-fleurs ou les arbres.
Dans chaque exemple, une petite partie
a la même forme que l'ensemble.
On appelle aussi cela une distribution d'échelle libre,
parce que quelque soit l'échelle, elle est la même.
Elle est donc libre de toute échelle.
Voici la distribution de degré approximative du web.
Il a été observé empiriquement
que le nombre de nœuds avec un degré k
est proportionnel à 1/k^2.
Ce type d'expression mathématique correspond à la loi de puissance,
parce qu'elle fait appel à une variable élevée à une certaine puissance.
Ici, 1/k^2 est équivalent à k^-2.
Si vous avez déjà entendu parler de distribution d'échelle libre,
vous savez que c'est équivalent à une distribution par loi de puissance.
Il faut donc savoir à quoi correspond cet exposant.
La définition d'un réseau d'échelle libre est donc:
un réseau qui présente une distribution libre d'échelle
ou de loi de puissance.
Nous avons vu que les réseaux d'échelle libre
sont similaires au fractales.
Voici un petit réseau d'échelle libre:
il est fractal, car il y a des hubs
qui ont beaucoup de liens sortants ou entrants,
et si on s'en approche, on voit à ce niveau de petits hubs.
À chaque niveau, on trouve des hubs de plus en plus petits,
qui ont la même forme que le réseau original.
Il y a donc autosimilarité, jusqu'à un certain point,
dans ce réseau, que j'appelle "de type fractal".
C'est pour cette raison qu'il présente
une distribution suivant un type de loi de puissance.
Je dis "un type de loi de puissance", car
dans le monde réel, les réseaux ne sont pas vraiment
libre de tout échelle.
De la même manière, dans le monde réel,
il n'y a pas de vrai objet fractal,
pas au sens mathématique.
Il y a des objets approximativement fractals.
Et c'est la même chose avec la distribution
du degré dans les réseaux.
Il faut noter aussi que les réseaux d'échelle libre
présentent aussi des propriétés de petit monde,
c'est-à-dire une faible distance moyenne entre nœuds,
et un taux élevé de clustering.
En 1999, Albert-Lázló Barabási et Réka Albert ont publié
un article dans la revue Science, appelé
"Émergence de l'échelle dans les réseaux aléatoires"
dans lequel ils ont introduit cette idée
de réseaux d'échelle libre
pour un grand public.
Comme l'article de Watts et Strogatz, dont j'ai déjà parlé,
il a eu un grand impact sur le jeune domaine de recherche
de la science des réseaux.
Barabási et Albert ont observé de nombreux types de réseaux,
à partir de données empiriques,
et ils en ont conclu que les distribution de degré en échelle libre
sont très courantes dans les réseaux complexes du monde réel.
D'autres articles, tels que celui-ci,
écrit par Clauset, Shalizi et Newman,
ont critiqué l'affirmation selon laquelle
les données suivent une distribution par loi de puissance.
Je voudrais que vous soyez conscients du fait
qu'il y a un débat sur la question de savoir si
certain réseaux sont vraiment d'échelle libre ou non.
Evelyn Fox Keller, une biologue qui étudie les réseaux,
a dit en 2005 que
"Les estimations actuelles de la présence de lois de puissance sont
probablement surestimées."
Et c'est probablement vrai,
mais d'une manière générale,
ce que la plupart des gens acceptent,
c'est que beaucoup de réseaux du monde réel,
la plupart d'entre eux, en fait,
ont une distribution de degré en longue queue.
Soit, une forme telle que celle-ci, où
beaucoup de nœuds ont peu de connexions,
par rapport au nombre de ceux qui ont un degré élevé.
C'est ce que l'on appelle la queue de la distribution
en probabilités, parce que cela ressemble à une queue.
Voici le corps, et voici la queue.
Elle est dite longue car elle continue encore et encore.
C'est complètement différent de ce qu'on appelle
une distribution en cloche normale:
voici la photo d'une distribution normale de la taille humaine.
C'est un bon exemple parce que les gens sont alignés
d'après leur taille.
Les plus petits sont ici,
et les plus grands ici.
Vous pouvez voir que la majorité est rassemblée au milieu.
Il y a peu de gens très petits, ou très grands.
La plupart est dans la moyenne.
Cette distribution normale n'a pas de longue queue.
Elle tombe très vite à zéro, de chaque côté.
Une distribution par loi de puissance, ou en longue queue,
ne tombe pas à zéro.
Elle diminue très lentement.
Et cela a des conséquences importantes pour les réseaux réels.