Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 18 Septembre 2012

Finding Homogeneous Collections of Dense Subgraphs using Constraint-Based Data Mining Approaches

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr