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

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.