LATAPY Matthieu

Хабилитация
Подразделение : NPA
Окончание контракта : 30.11.2007
https://lip6.fr/Matthieu.Latapy

Grands Graphes de Terrain - Mesure et Metrologie, Analyse, Modelisation, Algorithmique

Graphes de Terrain. Dans de nombreux contextes des grands graphes jouent un rôle essentiel ; citons par exemple la topologie de l'Internet, les graphes du Web ou les échanges Pair-à-Pair, mais aussi les réseaux sociaux, biologiques ou linguistiques. La disponibilité de données massives, de capacités de traitement adéquates, et l'observation de diverses propriétés en commun ont récemment donné naissance à un vaste effort de recherche sur ces ob jets. Son originalité réside dans le fait qu'on part de graphes issus d'observations, et non définis formellement. C'est en ce sens que ce sont des graphes de terrain. Afin de développer une expertise globale du domaine, je me suis impliqué dans les différentes problématiques qu'il soulève. Elles se regroupent en quatre familles complémentaires. Mesure et Métrologie. Mener des mesures fiables, de qualité et à grande échelle est une problématique de recherche en soi, à laquelle j'ai contribué [19,27,34]. Au-delà, les données obtenues étant en général partielles et biaisées, il est crucial d'en estimer la pertinence. J'ai ainsi travaillé à la définition du problème [8] et son traitement dans le cas de la topologie de l'internet [4,19,23,34]. J'ai plus récemment proposé la première méthode rigoureuse pour évaluer le crédit qu'il est raisonnable d'accorder aux propriétés observées en pratique [36]. Analyse. Jusqu'à la fin des années 90, il n'y avait que très peu d'outils pour décrire les grands graphes de terrain. Aujourd'hui les manques restent importants, notamment pour certaines classes de graphes. J'ai proposé en ce sens un ensemble de notions pour l'analyse des réseaux bipartis [1,25,27], une classe importante en pratique. J'ai par ailleurs proposé l'un des deux meilleurs algorithmes actuellement disponibles pour la recherche de communautés (sous-graphes denses faiblement liés vers l'extérieur) [3,20] : les autres algorithmes sont bien plus limités dans la taille des graphes traitables ou produisent des communautés de qualité bien moindre. Modélisation. Une fois les principales propriétés d'un graphe identifiées, les capturer dans un modèle formel est crucial notamment pour les expliquer, obtenir des résultats formels, et mener des simulations. Dans cette optique, j'ai proposé un modèle capturant les principales propriétés de base des grands graphes de terrain, tout en gardant un caractère aléatoire essentiel pour mener des études formelles [5,9,28]. Malgré la forte concurrence, le modèle proposé se positionne parmi les plus pertinents existants. Algorithmique. La taille des graphes considérés interdit l'utilisation d'algorithmes quadratiques ou plus ; de nombreux problèmes pour lesquels des solutions habituellement satisfaisantes sont connues doivent donc être retravaillés. Par ailleurs, la présence de propriétés caractéristiques des graphes de terrain ouvre la voie au développement d'algorithmes effcaces dans ces cas (et pas forcément en général). J'ai ainsi proposé pour l'énumération des triangles [35] et le calcul du diamètre [40] des algorithmes permettant des calculs jusqu'alors inaccessibles. J'ai utilisé certaines propriétés des graphes de terrain pour démontrer les performances de ces algorithmes. Méthodologie. Mon approche repose sur un aller-retour permanent entre questions fondamentales et problèmes appliqués. Ainsi, des cas pratiques ont soutenu, guidé et complété mes développements (notamment la topologie de l'Internet, les échanges au niveau ip, et les échanges Pair-à-Pair), et mes publications sont accompagnées d'implémentations dans tous les cas où c'est pertinent. Perspectives. Outre une vue d'ensemble du domaine, structurée autour de mes propres contributions, mon mémoire présente les perspectives qui me semblent les plus importantes pour les années à venir. J'insiste notamment sur : le développement de mesures axées sur l'identification fiable de propriétés ciblées (par opposition aux mesures cherchant à être aussi vastes que possible) ; l'importance, pour notre compréhension des grands graphes de terrain, de l'analyse de leur structure en communautés multi-échelles et se recouvrant partiellement ; et sur l'étude des dynamiques de graphes (i.e. leur évolution temporelle).

Защита диссертаций : 30.11.2007

Научный руководитель

2 Аспиранты (Научны(е)й руководител(и)ь / Со-руководитель)

24 Кандидаты наук 2007 - 2021

Mentions légales
Карта сайта