Pierre-Nicolas Mougel (INSA Lyon)

Le contexte des travaux présenté est la fouille de données sous contraintes de graphes attribués. Il s’agit de graphes dans lesquels des propriétés, encodées sous forme d’attributs, sont associées à chaque sommet.

Dans ce type de données, nous proposons deux approches pour la recherche de motifs formés par des collections de sous-graphes denses et tels que les sommets partagent suffisamment d’attributs. La première approche est basée sur des motifs nommés Ensembles Maximaux de Cliques Homogènes. Ces motifs satisfont des contraintes concernant le nombre de sous-graphes denses, la taille des sous-graphes et le nombre d’attributs partagés. La seconde approche, basée sur des motifs nommées Collections Homogènes de k-cliques Percolées, emploie quant à elle une notion de densité plus relaxée permettant d’adapter la méthode aux données incomplètes.

Ces deux méthodes sont appliquées à l’analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d’interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision.