L'analyse de l'historique des conversations (fichiers log) entre services afin de découvrir les protocoles de conversations sous-jacents, aussi appelés protocoles métiers, est devenue un vrai challenge. Le comportement des services web est spécifié dans les protocoles métiers, ce qui montre l'importance de ces derniers. La génération des protocoles métiers passe d'abord par la corrélation des messages dans les logs en conversations. Cette tâche est facilement réalisable si on suppose que les logs contiennent des identifiants qui permettent d'associer chaque message à une conversation. Mais malheureusement, cette information est rarement existante dans les logs. Notre travail s'inscrit dans cette thématique, tel qu'il consiste à corréler les messages des logs des services web en conversations. Pour ce faire, contrairement aux autres approches, aucune supposition n'est faite concernant l'existence de l'identifiant des conversations. Notre approche consiste à modéliser les logs sous forme de graphes et à utiliser des techniques de la théorie des graphes pour extraire les conversations. Par ailleurs, les logs sont souvent incomplets et contiennent des erreurs. Ce qui induit une certaine incertitude des résultats. Afin de prendre en compte cette incertitude, nous introduisons la théorie de l'évidence de Dempster-Shafer. Notre approche a été implémentée et testée sur des logs générés.