Les graphes sont communement utilises en tant que modele abstrait permettant de representer des relations complexes qui impliquent des couples d'individus. Chaque relation s'y voit associee a une arrête qui relie deux sommets du graphe. On peut par exemple citer le cas des graphes construits a partir de reseaux sociaux et ou les arr^etes representent des relations d'amities entre utilisateurs ou le cas des graphes issus de reseaux informatiques ou chaque arr^ete decrit une connexion entre deux serveurs. Au cours des annees 1970, la notion d'hypergraphe a ete introduite a n de modeliser des relations plus complexes, impliquant potentiellement plus de deux individus. Ce nouveau formalisme a donne lieu a de nombreuses applications dans des domaines aussi divers que la bio-informatique, la vision par ordinateur ou encore le traitement du langage naturel. Cependant, et a l'instar des graphes, ce nouveau modele se montre limite des lors que l'on considere des relations entre ensembles d'individus. A titre d'illustration, on peut citer le cas des jeux competitifs a plusieurs joueurs: chaque partie peut en e et ^etre consideree comme une relation liant (au minimum) deux equipes de joueurs (victoire, defaite, egalite). Des relations similaires peuvent intervenir dans le cadre de reseaux sociaux (relations entre groupes d'individus) ou dans le cadre de reseaux informatiques (relations entre clusters). Dans le cadre des problemes listes ci-dessus, il est imperatif de prendre en consideration a la fois les individus et les ensembles. Dans le cadre de cette these, nous introduisons un nouveau modele appele graphe d'hypernuds (hypernode graph) permettant de representer speci quement des relations binaires entre ensembles d'individus. Nous proposons egalement une extension des notions de Laplacien de graphe et de noyau de graphe pour cette nouvelle classe d'objets. Nous montrons que cette extension est coherente avec la theorie spectrale de nie dans le cadre des graphes non diriges. De plus, nous montrons que nos Laplaciens sont strictement plus expressifs que les Laplaciens de graphe. On notera que cette propriete est speci que a notre classe d'objets et n'est pas veri ee par exemple dans le cas des Laplaciens d'hypergraphe. A l'aide de ces nouveaux outils, nous sommes capables de de nir des algorithmes d'apprentissage ecaces pour les graphes d'hypernuds. Sur ces bases, nous proposons une nouvel algorithme permettant d'evaluer les niveaux de competence individuels dans des jeux a plusieurs joueurs (skill rating). Nous evaluons la qualite de nos resultats via un schema predictif (nous predisons le resultat de nouveaux matchs a l'aide des valeurs precedemment calculees). Les resultats experimentaux montrent que nous sommes en mesure d'obtenir des resultats competitifs vis-a-vis d'algorithmes specialises. Nous etudions en detail les principales proprietes des graphes d'hypernuds et mettons en evidence des relations fondamentales avec les graphes signes.
- Directeur : Rémi Gilleron (Professeur à l'Université de Lille) - Rapporteurs : Mark Herbster (Lecturer at University College London), Francois Denis (Professeur à l'Université d'Aix-Marseille) - Examinateurs : Sophie Tison (Professeur à l'Université de Lille), Marc Tommasi (Professeur à l'Université de Lille), Yannick Cras (Chief Development at SAP SE), Gemma Garriga (Data Scientist at Allianz SE)
Thèse de l'équipe MAGNET soutenue le 23/01/2015
français
English