Algorithmes de routage et modèles aléatoires pour les graphes petits mondes

L’effet petit monde et la navigabilite

L’effet petit monde tient son nom de l’expression populaire « le monde est petit »designant la surprise de constater que deux connaissances d’un m éme in- ˆ dividu, a priori sans rapport, se connaissent entre elles. L’etude des relations sociales en tant que reseau d’interactions date des ann ées 30, en particulier la creation par le psychologue Jacob-Levy Moreno de la sociom étrie. Celle-ci a pour but la mesure objective des relations sociales au sein d’un groupe. C’est dans une periode ult érieure de d éveloppement de la science des réseaux sociaux que les psy- chologues se sont interessés a l’effet petit monde [TM69, dSPK78, KB78]. En particulier, Stanley Milgram a effectue une expérience sociologique en 1967 [Mil67] én demandant a 300 habitants du Nebraska et de Boston de faire parvenir une lettre a un habitant de Boston dont ils ne connaissaient que le lieu d’habitation et la profession, en ne la retransmettant qu’a une personne qu’ils connaissaient Introduction 9 personnellement (et en iterant le processus jusqu’ à atteindre la personne cible). Relativement peu de lettres sont arrivees à destination (environ un quart), mais  le resultat surprenant fut que la longueur moyenne d’une cha  îne de porteurs du message de son origine a sa destination etait tr és faible (5,2) en regard du nombre d’individus et de leur eloignement g éographique et social. Cette exp érience a par àilleurs eté reproduite r écemment par Dodds ét al. [DMW03] sur 60 000 individus, echangeant cette fois des é-mails, et a aboutit a des cha înes de messages de longueur moyenne 4,1 entre individus de continents differents. On pourrait pen- ser qu’il n’est pas vraiment surprenant que les chaînes soient si courtes, puisqu’en supposant que chaque individu ait seulement 10 connaissances, chacun pourrait a priori atteindre 106 individus a distance 6. Mais les r eseaux sociaux presentent un fort coefficient de clustering, il est donc probable que les connaissances immediates d’un individu n’aient qu’une seule connaissance étrang ére a ce voisinage, et que l’on atteigne seulement 11 individus a distance 2 par exemple, c’est pourquoi cette proprieté est remarquable. La notion de petit monde n’a pas aujourd’hui de definition formelle ; elle est definie, dans certains articles ([WS98]), comme la combinaison d’un fort coeffi- cient de clustering et d’un petit diametre. L’objet de cette th ese est d’approfondir l’explication dynamique et algorithmique de ce phenom éne propos ee par Klein- berg en 2000 [Kle00] qui y introduisit la notion de navigabilite. Il s’agit de caracteriser non seulement la longueur des chemins, mais aussi la fac¸on dont ils sont decouverts. Dans l’exp érience de Milgram, les individus n’utilisent que leurs contacts locaux pour renvoyer la lettre ; il s’agit donc d’un routage decentralis é, en ce sens que l’on n’utilise qu’une vue locale du reseau pour transmettre le mes- sage. C’etait aussi le cas de la navigation à travers le r eseau des pages web il y a quelques annees 1 , qui se faisait d’une page a l’autre sans conna ître la carte globale du reseau [AJB99, Kai99]. Par ailleurs, la d écouverte des chemins de fac¸on decentralis ée est une n écessit é pour les r éseaux d’interactions r éels qui com- portent un tres grand nombre de sommets et o u une recherche classique des plus courts chemins n’est pas possible, car tres co uteuse en temps. ˆ La proprieté de navigabilit é de l’effet petit monde est une caract érisation plus specifique que la propri été de petit diam étre utilis ee jusqu’alors, pour le d éfinir. én particulier, meme si un réseau al éatoire uniforme pr ésente un diam étre lo- garithmique en le nombre de noeuds, Kleinberg montre qu’il n’existe aucun algorithme decentralis é qui puisse d écouvrir ces chemins courts ( i.e. polylogarithmiques) [Kle00]. On appellera par la suite petit monde navigable tout reseau dont le diametre est polylogarithmique en le nombre de noeuds, et dont les chemins po- lylogarithmiques peuvent etre calculés par un algorithme d écentralis é. On parlera 1Aujourd’hui, l’utilisation massive de moteurs de recherche comme Google pour acceder aux pages web nous amene n eanmoins à nuancer ce fait. 10 Introduction simplement de petit monde lorsqu’il n’y a pas d’ambigu¨ıte. Problematiques des petits mondes navigables én etudiant l’effet petit monde sous l’angle algorithmique de la navigabilit é, nous abordons le probleme de la compr ehension d’un ph énom éne r eel qui contient des problematiques fondamentales pour l’informatique. Comprehension de l’effet petit monde. La comprehension du ph énom éne petit monde observe dans les réseaux sociaux contient deux questions essentielles : – quel est le type d’algorithme de routage decentralis é utilis é pour transmettre un message dans un reseau social ? – existe-t-il une structure sous-jacente particuliere qui permet la construction d’un reseau petit monde navigable ? Ces questions sont intimement liees puisque l’algorithme de routage utilise la structure du reseau pour naviguer. Dans cette th ése, nous allons d ecrire ces deux àspects du probleme comme l’aspect dynamique et l’aspect structurel de l’effet petit monde : – d’une part, un reseau petit monde navigable doit avoir une structure qui presente un faible diam étre et qui permet de stocker de mani ere locale les informations requises pour evaluer les positions relatives des noeuds (aspect structurel) ; – d’autre part, il doit exister un processus de routage decentralis é qui peut en tirer parti (aspect dynamique). Nous traiterons l’aspect dynamique dans la premiere partie de ce document et l’aspect structurel dans la seconde. Problematiques informatiques des petits mondes. Ces dernieres ann ees, le reseau Internet a connu un changement d’ échelle rendant irr éalistes des algo- rithmes de routage centralises. Le d éveloppement des algorithmes d écentralis és qui n’utilisent qu’une vue locale du reseau a permis de passer à grande echelle ét de creer de nouveaux grands r éseaux informatiques totalement d écentralis és, comme les réseaux pair- à-pair. Un protocole pair- a-pair est un protocole d’echange de fichiers entre ordinateurs jouant tous le m éme role, c’est-a-dire qu’il n’y a pas, en genéral, de serveur central (on peut citer les réseaux CAN [RFH +01] et Chord [SMK+01]). Outre la proprieté de passage à l’ echelle, un tel r éseau presente également une bonne r ésistance aux pannes et aux attaques cibl ées, contrairement a un r eseau centralis é, puisque la mise hors service d’un des or- dinateurs du reseau a peu d’influence sur son fonctionnement global. Par ailleurs, les fichiers echang és sur les r éseaux pair- à-pair sont souvent de grande taille (fi- Introduction 11 chiers video), il est donc n écessaire de construire des algorithmes d édi és qui sont decentralis ését calculent des chemins courts. La specificit é du routage dans les grands réseaux informatiques d écentralis és et dans les petits mondes est donc si- milaire ; nous verrons dans cette these que cette sym etrie permet un va-et-vient tres riche entre les probl emes et applications de l’un et l’autre domaine. On dis- tingue deux problematiques principales de l’effet petit monde pour l’informa- tique : – construire de nouveaux algorithmes decentralis és efficaces, d édi és aux grands réseaux ; – construire de nouvelles architectures de grands réseaux de petit diam étre, dont les chemins courts peuvent etre calcul ˆ es de fac¸on d écentralis ée. Modeles pour les r eseaux d’interactions Dans la premiere partie de cette th ese, nous commenc¸ons par baser notre etude de l’aspect dynamique de l’effet petit monde sur le seul mod éle de pe- tit monde navigable existant au debut de cette th ése : le mod ele de Kleinberg. Dans la deuxieme partie, nous nous employons avec succ es a d efinir un mod éle plus genéral. De nombreux mod éles ont eté introduits pour repr ésenter les r éseaux d’interactions, ou certaines de leur proprietés statistiques, et ont inspir é le mod éle de Kleinberg. Nous rappelons les principaux dans cette section. Un reseau se repr ésente de fac¸on naturelle par un graphe. Nous utiliserons dans toute la suite l’un ou l’autre vocabulaire de fac¸on indifferenci ée : un noeud correspond a un sommet et un lien a une arete ˆ . On trouvera la definition formelle d’un graphe dans le preambule. Graphe aleatoire uniforme d’Erd os et R ¨ enyi. Le premier graphe etudi é comme un modele possible pour les r eseaux r éels fut le graphe al éatoire G(n, p) d’Erdos¨ et Renyi [ER59]. Il s’agit d’un graphe al éatoire uniforme sur n sommets ou il existe une arete entre deux sommets avec une probabilit ˆ e p constante. Cet objet mathematique a été tr és etudi é, on pourra se r éférer à [Bol85] pour une vue d’ensemble des resultats. Nous nous int éressons seulement ici à son r ole ˆ historique en tant que modele pour les r eseaux d’interactions, car il était consid éré jusqu’a r ecemment comme le seul mod éle, par d efaut, pour les réseaux réels. Or les recentes observations exp érimentales (qui étaient impossibles ou tr és partielles auparavant) ont mis en lumiere d’importantes diff erences. Ainsi, la distribution des degres suit une loi de Poisson (exponentielle), alors qu’il s’agit d’une loi de puissance pour la grande majorite des r éseaux r éels. Il s’agit l à d’une difference importante puisqu’elle caract érise l’h étérog énéit é du r éseau. Les noeuds jouant tous le meme r ˆ ole dans un graphe d’Erd ˆ os-R ¨ enyi, le graphe ne 12 Introduction possede pas de propri eté discriminante, et les degr és sont naturellement r épartis de fac¸on egale autour de la moyenne. Pour la m éme raison, ce graphe présente un faible coefficient de clustering, puisque les voisins d’un noeud n’ont aucune raison d’etre davantage reliés entre eux que deux noeuds pris au hasard. Enfin, meme si ce graphe pr ˆ esente un diam étre polylogarithmique en le nombre de sommets, on peut montrer que tout algorithme decentralis é y calcule des chemins de longueur au moins polynomiale [Kle00] ; ce n’est donc pas un petit monde navigable. Ces differences ont montr é l’importance de trouver un mod éle plus fid ele. Modele d’Albert et Barabasi pour la distribution des degr es. Suite a la decouverte de distributions de degr és suivant une loi de puissance dans de nombreux réseaux r éels, la construction de nouveaux mod éles a eté dirig ée vers la reproduction de cette proprieté. En 1999, Albert et Barabasi [BA99] ont popularise un mod éle dynamique permettant d’obtenir une distribution des degres suivant une loi de puissance. Ce mod éle consiste a construire un reseau noeud par noeud, en reliant chaque nouveau noeud pr éférentiellement àux sommets existants de plus hauts degres. Il est connu sous le nom de l’attachement preférentiel . Des processus similaires avaient eté introduits d és les annees 20 par des math ématiciens [EP23, Yul24, Zip49], puis étudi és en sociologie [Sim55, dSP76], mais ce fut la premiere etude de ce processus en tant que modele d’un ph enom éne physique. L’int erét de ce mod ˆ ele est sa construction dynamique, puisque dans de nombreux réseaux r éels, des noeuds et des liens sont frequemment ajout és et enlev és au cours du temps (on peut penser au r éseau des pages web par exemple). Nous presentons maintenant les deux principaux mod éles qui ont eté developp és sp écifiquement pour reproduire l’effet petit monde. Modele de petit monde non navigable de Watts et Strogatz. En introduisant la notion formelle de coefficient de clustering, Watts et Strogatz [WS98] ont propose un modele qui pr esente à la fois un petit diam etre et un fort coefficient de clustering. Une variante du modele a egalement été développ ée et analys ée par Newman ét Watts [NW99]. Le modele est construit de la fac¸on suivante : a partir d’un an- neau regulier de n sommets et k aretes par sommet, distribu ˆ ees r éguli érement par rapport a leur origine, on redirige ind ependamment chaque extr émit é d’ar éte avec ˆ une probabilite p constante, donnee en param étre, vers un sommet de l’anneau choisi de maniere al eatoire uniforme. La figure 2 illustre ce mod éle pour p = 0, p = 1 et une valeur intermediaire 0 < p < 1 qui donne lieu a l’apparition des deux proprietés de petit diam étre et fort clustering simultanement. Le nombre k d’aretes de d ˆ epart n’influe pas sur le mod éle.