Evaluation rapide du diamètre d'un graphe.

Resume. Lors de l’analyse de graphes, il est important de connaitre leurs proprietes afin de pouvoir par exemple identifier leur structure et les comparer. Une des caracterisations importante de ces graphes repose sur le fait de determiner s’il s’agit ou non d’un "petit monde". Pour ce faire, la valeur du diametre du graphe est essentielle. Or la mesure du diametre est pour un tres grand graphe, une operation extremement longue. Nous proposons un algorithme en deux phases qui permet d’obtenir rapidement une estimation du diametre d’un graphe avec une proportion d’erreur faible. En reduisant cet algorithme a une seule phase et en acceptant une marge d’erreur plus elevee, nous obtenons une estimation tres rapide du diametre. Nous testons cet algorithme sur deux grands graphes de terrain (plus d’un million de nœuds) et comparons ses performances avec celles d’un algorithme de reference BFS (Breadth-First Search). Les resultats obtenus sont decrits et commentes.