Reconnaissance dynamique des graphes de permutation et estimation de la distribution des degrés de l’Internet.

Séminaire de Christophe Crespelle <christophe.crespelle@lip6.fr> le 26  mai 2010 à 11h00, ENS de Lyon, amphi A

Résumé:

L’exposé comprend deux parties assez largement indépendantes.

Dans la première, on considère un graphe de permutation soumis à des
modifications élémentaires de sa structure : l’ajout ou le retrait d’une
arête ou d’un sommet (avec les arêtes définissant son voisinage).
L’algorithme de maintien dynamique traite chacune de ces quatre
opérations en temps O(n). Il détermine après chaque modification si le
nouveau graphe est encore un graphe de permutation. Si la réponse est
positive, un modèle d’intersection en est fourni, sinon l’algorithme
s’arrête. Pour cela, nous utilisons la décomposition modulaire des
graphes.

La seconde partie de l’exposé présente une méthode d’estimation
rigoureuse de la distribution des degrés de l’Internet, qui est une
propriété fondamentale du réseau.
La méthode classique d’estimation de cette distribution est basée sur la
collecte d’un échantillon aussi grand que possible du graphe, dont il a
été montré qu’il conduisait a une estimation erronée de cette propriété.
Ici nous posons les bases d’une nouvelle méthode qui permet de
s’affranchir de cette difficulté. Elle consiste à déterminer
rigoureusement le degré d’un noeud du coeur du réseau en lançant des
traceroutes vers lui depuis un grand nombre de moniteur. Nous présentons
et analysons les résultats obtenus sur un exemple de mesure.