Maintenance et simulation de graphes aléatoires dynamiques

Abstract

Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit.