JdS2012


 English   -  Français  

Résumé de communication



Résumé 193 :

Comparaison des méthodes de classification non supervisée des noeuds d'un graphe
Leger, Jean-Benoist ; Daudin, Jean-Jacques ; Vacher, Corinne
INRA, UMR 518 MIA AgroParisTech/INRA

La classification non supervisée des n?"uds d'un graphe est un sujet en plein développement possédant des applications dans nombre de domaines. Deux définitions de cluster sont possibles. Celle couramment utilisée, consistant à considérer qu'un cluster est un ensemble de n?"uds fortement liés dans le graphe, ce type de cluster est nommé communauté. La seconde consistant à dire qu'un cluster est un ensemble de n?"uds possédant un rôle proche dans la structure de graphe. Ce type de cluster est nommé ensemble structurellement homogène de n?"uds. Ces deux définitions sont différentes: en effet deux n?"uds peuvent avoir exactement les mêmes connexions dans le graphe, sans qu'ils soient liés. Toutefois lorsque la structure d'un graphe est totalement expliquée par la présence de communauté, alors les ensembles structurellement homogènes de n?"uds seront ces communautés. Les méthodes de détection de communautés ont fait récemment l'objet d'une revue par Fortunato. Nous effectuons dans cette communication une revue des méthodes de clustering de graphe. Des simulations ont été effectuées sur des graphes bipartites non valués, afin de comparer l'efficacité de classification d'une partie de ces méthodes.