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

Oussama Allali

26 mai 2011 à 11h : salle 25-26/101

Slides

Beaucoup de graphes de terrain, comme les relations acteur-film ou fichier-fournisseur, ont une nature bipartie et sont modélisés par des graphes bipartis, dont les nÅ“uds sont divisés en deux ensembles avec des liens entre des nÅ“uds de différents ensembles seulement. Cependant, il y a actuellement un manque de méthodes pour analyser correctement ces graphes, la plupart des méthodes existantes étant conçues pour des graphes classiques. Une approche courante, mais qui a des limites, consiste à transformer les graphes bipartis en graphes classique, par un procédé appelé projection. Cependant ceci entraîne une perte importante d’informations. Dans cet exposé je présenterai les liens internes et je les proposerai 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. Jemontreraien é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 les ressemblances et les différences entre les graphes deterrainbipartis et les graphes bipartis aléatoire. 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 nÅ“uds 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 classiques (non-bipartis). Toutefois, leurs méthodes ne sont pas directement applicables à, ou appropriées pour, les graphes bipartis. Je présenterai une approche basée sur les liens internes pour la prédiction dans les graphes bipartis. Je montrerai que notre méthode fonctionne très bien, beaucoup mieux que l’approche de recommandation classique.