MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEStructure des grands réseaux d'interaction et dynamique de graphe par Christophe Crespelle
Date : | 24/11/09 | Time : | 10:30 | Location : | Euler Violet |
L'exposé abordera deux problématiques de façon indépendante. La première touche à la modélisation des grands réseaux d'interaction. Les modèles offrent les propriétés à exploiter pour la conception des outils d'analyse et de contrôle des réseaux (traitement algorithmique, définition de protocoles). D'autre part, en rendant possible la génération aléatoire de réseaux, ils permettent de tester et de valider par simulation les solutions développées. Enfin, ils fournissent les moyens mathématiques de prouver les performance de ces solutions. Pour toutes ces raisons, la définition de modèles réalistes revêt des enjeux majeurs. A l'heure actuelle, la modélisation des réseaux complexes par des graphes reposent principalement sur des propriétés numériques, comme la distribution des degrés des noeuds du réseaux et le coefficient de clustering. Deux problèmes surgissent de cette approche : il est difficile de générer aléatoirement des réseaux ayant les propriétés souhaitées pour ces deux paramètres, et pire, les réseaux générés par cette approche ne ressemblent pas autant qu'escompté à ceux rencontrés en pratique. Nous proposons de solutionner ces deux problèmes par une approche faisant jouer un rôle prépondérant à la structure de graphe de ces objets. On cherche ici à reproduire les propriétés de forte agglomération locale et de faible densité locale en s'intéressant à l'agencement des cliques, en particulier à leur chevauchement.
La deuxième problématique abordée sera celle du maintien dynamique de structures de graphe. Ces problèmes sont en général très difficiles. Ici, nous nous intéressons au cas d'une classe de graphe fortement structurée : celle des graphes d'intervalles. Ce sont les graphes dont les sommets peuvent être mis en bijection avec un sous-ensemble d'intervalles de la droite des réels de sorte qu'il y a une arête entre deux sommets dans le graphe ssi leurs intervalles correspondants s'intersectent. Il s'agit d'être capable, étant donné un graphe d'intervalles, de déterminer si une modification élémentaire du graphe, qui peut être l'ajout ou la suppression d'une arête ou d'un sommet (avec les arêtes définissant son voisinage), respecte la structure d'intervalles. Autrement dit, on veut déterminer si le nouveau graphe est encore un graphe d'intervalles et en donner un modèle d'intersection si tel est le cas. On montre que n'importe quelle modification élémentaire peut être traitée de la sorte en temps O(n), où n est le nombre de sommets du graphe.
Page des séminaires
|