Réinitialiser mot de passe
E-mail
Password
RNTI

MODULAD
Evaluation rapide du diamètre d'un graphe
In EGC 2012, vol. RNTI-E-23, pp.311-322
Résumé
Lors de l'analyse de graphes, il est important de connaître leurs propriétés
afin de pouvoir par exemple identifier leur structure et les comparer.
Une des caractérisations importante de ces graphes repose sur le fait de déterminer
s'il s'agit ou non d'un "petit monde". Pour ce faire, la valeur du diamètre
du graphe est essentielle. Or la mesure du diamètre est pour un très grand
graphe, une opération extrêmement longue. Nous proposons un algorithme en
deux phases qui permet d'obtenir rapidement une estimation du diamètre d'un
graphe avec une proportion d'erreur faible. En réduisant cet algorithme à une
seule phase et en acceptant une marge d'erreur plus élevée, nous obtenons une
estimation très rapide du diamètre. Nous testons cet algorithme sur deux grands
graphes de terrain (plus d'un million de noeuds) et comparons ses performances
avec celles d'un algorithme de référence BFS (Breadth-First Search). Les résultats
obtenus sont décrits et commentés.