ALLALI Oussama

Docteur
Équipe : ComplexNetworks
Date de départ : 30/06/2011
https://lip6.fr/Oussama.Allali

Direction de recherche : Matthieu LATAPY

Co-encadrement : MAGNIEN Clémence

Structure et dynamique des graphes de terrain bipartis : liens internes et prédiction de liens

Beaucoup de graphes de terrain comme les relations acteur-film ou fichier-fournisseur sont modélisables par des graphes bipartis, dont les noeuds sont divisés en deux ensembles avec des liens entre les noeuds de différents ensembles seulement. Cependant, des méthodes manquent actuellement pour analyser correctement ces graphes, la plupart des méthodes existantes étant conçues pour des graphes classiques. Une approche courante, mais limitée, consiste à transformer les graphes bipartis en graphes classiques, par un procédé appelé projection. Cependant ceci entraîne une perte importante d'informations. Nous introduisons dans cette thèse les liens internes, et les proposons comme une nouvelle notion importante pour analyser les graphes de terrain bipartis : elle permet de mesurer la redondance dans ces graphes, et de mesurer la perte d'information entre un graphe biparti et ses projections. Nous montrons en étudiant différents jeux de données que les liens internes sont très fréquents, et que les statistiques associées permettent de souligner leurs ressemblances et leurs différences avec les graphes bipartis aléatoires. Ensuite, nous montrons que nous pouvons tirer profit de cette notion pour modéliser les graphes de terrain bipartis et les stocker dans un format compact.
La plupart des graphes de terrain sont de plus dynamiques, c'est-à-dire que leur structure évolue au fil du temps par l'ajout et/ou le retrait de noeuds et/ou de liens. L'étude de la dynamique des graphes de terrain peut s'aborder par le problème de la prédiction de nouveaux liens dans ces graphes. Plusieurs travaux ont étudié le problème de la prédiction de liens dans les graphes classique (non-bipartis). Toutefois, leurs méthodes ne sont pas directement applicables aux graphes bipartis ou sont inappropriées. Nous proposons une approche basée sur les liens internes pour la prédiction dans les graphes bipartis. Nous montrons que notre méthode fonctionne très bien, beaucoup mieux que l'approche de recommandation classique.

Soutenance : 24/06/2011

Membres du jury :

FLEURY Eric, Professeur, ENS de Lyon [Rapporteur]
ROUVEIROL Céline Professeur, Université Paris-Nord [Rapporteur]
GALLINARI Patrick Professeur, Université Pierre et Marie Curie
KERMARREC Anne-Marie Directeur de Recherche INRIA, Rennes
PRIEUR Christophe Maître de Conférences, Université Paris-Diderot
LATAPY Matthieu, Directeur de Recherche CNRS
MAGNIEN Clémence, Chargée de Recherche CNRS

Date de départ : 30/06/2011

Publications 2009-2013

Mentions légales
Carte du site