lipn

Laboratoire d'Informatique de Paris Nord

UMR 7030, Université Paris 13, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse

up13 cnrs

Analyse et fouille de graphes de terrain

 

L'étude et l'analyse de grands réseaux d'interactions, dits aussi graphes de terrain est un thème qui pose un ensemble des problèmes d'apprentissage difficiles. Ces graphes de terrain sont au centre d'un grand nombre d'applications, car ils permettent de modéliser naturellement des systèmes d'interactions complexes. Les graphes traités dans nos travaux sont des graphes biologiques (statiques), des réseaux sociaux vus à la fois sous leurs aspects statiques (apprentissage de communautés) et dynamiques (prévision de liens).

Réseaux d'interactions et données biologiques à grande échelle

L'équipe conçoit depuis plusieurs années des algorithmes d'apprentissage appliqués à des problèmes variés de bioinformatique, apprenant ou manipulant des graphes d'interaction.

Résultats :

  • Méthode de classification non supervisée de réseaux d'interactions locaux construits à partir de données à grande échelle [3], produisant des modules de gènes co-régulés plus pertinents que des groupes de gènes co-exprimés [2].
  • Méthode de classification non supervisée de structures protéiques [9], qui s'appuie sur un pré-traitement original du graphe des similarités structurales entre paires de protéines et applique une contrainte ternaire de transitivité pour filtrer les arêtes du graphe.

Prévision de liens

La prévision de nouveaux liens est un sous-problème de modélisation de l'évolution des graphes de terrain, qui a des applications concrètes importantes, notamment pour le calcul de recommandations. Nous nous sommes concentrés sur l'étude des graphes d'interaction bipartis dans le cadre d'une approche dite topologique, qui prévoit l'évolution d'un graphe en utilisant uniquement des indicateurs topologiques calculés à partir de son historique.

Résultats :

  • Mesures topologiques dyadiques spécifiques pour exprimer similarité entre nœuds dans un graphe biparti et dans les graphes projetés associés [1]. Ces nouvelles mesures permettent d'améliorer significativement la qualité du modèle de prévision de liens.
  • Application de l'approche précédente sur des graphes tripartis modélisant l'évolution de folksonomies [8]. Des expérimentations sur des données de folksonomies réelles montrent un net avantage de notre nouvelle approche par rapport au filtrage collaboratif en terme de précision desrecommandations.
  • Adaptation à un cadre supervisé de techniques classiques d'agrégation de préférences (non-supervisées) pour la prévision de liens [7]. La contribution de chaque attribut au modèle prédictif est apprise puis utilisée lors de l'agrégation des préférences.

Extraction de communautés

Les approches de prévision de liens décrites précédemment étant coûteuses lorsqu'elles sont appliquées à des grands graphes, nous souhaitons utiliser la structure en communautés des graphes étudiés (une communauté est un sous-graphe composé de nœuds plus liés entre eux qu'avec le reste du graphe), afin d'obtenir plus efficacement des modèles de prévision de liens.

Résultats :

  • Algorithme de détection de communautés éventuellement chevauchantes [4] qui identifie des nœuds meneurs de communauté, puis rattache les autres nœuds aux meneurs par des techniques d'agrégation de préférences. Le choix du rattachement à une communauté dépend des choix de ses voisins directs.
  • En collaboration avec l'équipe AOC (une thèse co-encadrée), proposition d'un algorithme de recherche des régions denses en 1 maximale, éventuellement chevauchantes, dans des matrices binaires bruitées. Cet algorithme combine un algorithme de graphes (flot maximal/coupe minimale), à une étape combinatoire énumérant des graines de régions denses [5]. Une extension récente de cette méthode met en place un mécanisme de semi-supervision par le biais d'une classification fournie a priori [6].

Références

      Nesserine Benchettara, Rushed Kanawati, and Céline Rouveirol. « A supervised machine learning link prediction approach for academic collaboration recommendation ». In

Proceedings of the 2010 ACM Conference on Recommender Systems, (RecSys 2010)

      , pages 253-256. ACM, 2010.

      Etienne Birmelé, Mohamed Elati, Céline Rouveirol, and Christophe Ambroise. « Identification of functional modules based on transcriptional regulation structure ».

BMC Proceedings

      , 2(Suppl 4):S4, Dec 2008. (Selected papers of Machine Learning in Systems Biology: MLSB 2007, 6 pages).

      Mohamed Elati, Pierre Neuvial, Monique Bolotin-Fukuhara, Emmanuel Barillot, François Radvanyi, and Céline Rouveirol. « Licorn: learning cooperative regulation networks from gene expression data ».

Bioinformatics

      , 23(18):2407-2414, 2007.

      Rushed Kanawati. « Licod: Leaders identification for community detection in complex networks ». In

PASSAT/SocialCom 2011, Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom)

      , pages 577-582. IEEE, 2011.

      Karima Mouhoubi, Lucas Létocart, and Céline Rouveirol. « Itemset mining in noisy contexts: A hybrid approach ». In

Proceedings of the 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2011)

      , pages 33-40. IEEE, 2011.

      Karima Mouhoubi, Lucas Létocart, and Céline Rouveirol. « A knowledge-driven bi-clustering method for mining noisy datasets ». In

Proceedings of the 19th International Conference On Neural Information Processing (ICONIP 2012), Part III

      , volume 7665 of

Lecture Notes in Computer Science

      , pages 585-593, Doha, Qatar, nov 2012. Springer.

      Manisha Pujari and Rushed Kanawati. « Link prediction in complex networks by supervised rank aggregation ». In

Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2012)

      , Athene, Greece, November 2012. IEEE.

      Manisha Pujari and Rushed Kanawati. « Tag recommendation by link prediction based on supervised machine learning ». In

Sixth International AAAI Conference on Weblogs and Social Media (ICWSM 2012)

      , pages 547-550, Dublin, june 2012. AAAI.

      Guillaume Santini, Henry Soldano, and Joël Pothier. « Automatic classification of protein structures relying on similarities between alignments ».

BMC Bioinformatics

    , 2012. (16 pages).

pres

w3c-xhtml