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
| 
