DS07 - Société de l'information et de la communication

Efficacité et structure pour les applications de la fouille de graphes – ESIGMA

Résumé de soumission

En tant qu'outil de modélisation, les graphes sont maintenant de plus en plus utilisés. Ils capturent les interactions entre des entités de manière facilement compréhensible tout en gardant un modèle riche de la structure sous-jacente. Les technologies de l'information nous permettent de collecter un grand nombre de données de divers domaines d'activités humains. Il devient donc vital de découvrir de l'information significative de ces données massives. Ces jeux de données peuvent être naturellement décris en tant que graphes: des exemples typiques sont les graphes web, la topologie d'internet, les réseaux sociaux et les corpus textuels. C'est le thème central de la fouille de graphes, dont les applications peuvent se trouver dans divers domaines tels la vision par ordinateur, la bioinformatique, la sociologie ou les sciences cognitives.

En parallèle, la théorie des graphes et le design d'algorithmes avec des bornes inférieures, en tant que domaine de l'informatique théorique, a montré des avancées considérables ces dernières années. Comme la plupart des problèmes combinatoires sont difficiles mathématiquement à résoudre, il est impossible d'obtenir un algorithme résolvant ces problèmes à la fois efficacement et de manière exacte. Les algorithmes d'approximation et les algorithmes paramétrés sont les principaux cadres utilisés pour concevoir des algorithmes avec des bornes (prouvables mathématiquement) sur leur temps d'exécution et leur garantie de performance. La théorie des graphes moderne propose un ensemble riche de résultats, dont la conception d'algorithmes à largement bénéficié également.

Les graphes obtenus depuis des applications réelles sont souvent très structurés. Par conséquent, apprendre et analyser cette structure est un problème important lorsqu'il s'agit de traiter ces jeux de données, en particulier lorsque les graphes sont gros. Ce projet vise à concevoir une vue structurelle des graphes obtenus depuis les jeux de données afin de concevoir et analyser des algorithmes sur un principe conscient de la structure plutôt que par des approche ad-hoc empiriques. L'innovation de ce projet réside dans le déploiement des connaissances en théorie des graphes et en conception et analyse théorique des algorithmes pour arriver à ce but. Plus particulièrement, nous utiliserons la théorie des graphes comme un guide pour naviguer dans les différents aspects structurels des données et nous utiliserons les avantages de l'analyse théorique d'algorithmes pour implanter et découvrir ces structures au sein des algorithmes.

Nous étudierons également les sujets nécessaires à la mise en \oe uvre d'applications concrètes telles que l'identification de nœuds influents lors du processus de diffusion de l'information et la détection d'évènements dans un flux de données issues de médias sociaux. Cette étude de structurelle, guidée par les besoins des applications, pourra bénéficier des méthodes étudiées dans (a), (b) et (c) et devra également s'appuyer sur d'importantes connaissances métiers liés aux données à disposition et aux domaines d'application.

De par sa nature, ce projet implique la collaboration interdisciplinaire. Notre consortium contient des experts dans les domaines pertinents au but et à la méthodologie de ce projet: l'apprentissage automatique, la fouille de graphes, la bioinformatique, la théorie des graphes structurelle, la conception et l'analyse d'algorithmes.

Coordinateur du projet

Laboratoire d'informatique de l'École polytechnique (Laboratoire public)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
Laboratoire d'informatique de l'École polytechnique

Aide de l'ANR 408 191 euros
Début et durée du projet scientifique : mars 2018 - 48 Mois

Liens utiles