Note ABES Classement dynamique et translation-synchronisation sur des graphes dynamiques Dynamic Ranking and Translation Synchronization on Dynamic Graphs Classement dynamique Graphes dynamiques Modèle BTL Modèle de translation-Synchronisation Statistiques en grande dimension Modèle Bradley-Terry-Luce Ranking Dynamic graphs BTL model Translation Synchronization model High dimensional statistics Graphes dynamiques Estimation de paramètres Modèles paramétriques (statistique) Moindres carrés Théorie spectrale (mathématiques) Le classement et les comparaisons apparaissent dans de nombreuses applications de la vie de tous les jours, telles que les tournois sportifs ou les systèmes de recommandation. Dans ces domaines, les données sont souvent composées de comparaisons appairées entre un ensemble d'objets, qui peuvent être résumées dans un graphe de comparaison. De nombreux modèles paramétriques pour les problèmes de classement ont été introduits, tels que le modèle de Bradley-Terry-Luce (BTL), dans lequel on suppose que les objets possèdent une qualité sous-jacente. Le classement est ensuite déduit des scores de qualité. De nombreux algorithmes d'estimation ont été analysés ces dernières années, comme l'algorithme de maximum de vraisemblance ou une méthode spectrale. Cependant, les classements et préférences personnelles peuvent évoluer avec le temps. Afin de prendre cela en compte, nous allons considérer une suite de graphes de comparaison, ou un graphe dynamique, qui rassemble les données à divers points de temps.Nous allons d'abord étudier une extension du modèle BTL au cas dynamique, introduit par Bong et al. en supposant que les scores de qualités sont Lipschitz. Notre algorithme est basé sur la méthode des plus proches voisins et sur l'algorithme de Rank Centrality, méthode d'estimation bien connue dans le cas statique. Nous fournissons des bornes [dollar]ell_2[dollar] et [dollar]ell_infty[dollar] pour notre estimateur et montrons les performances de notre algorithme sur des données réelles et synthétiques.Dans un second temps, nous introduirons une version dynamique du modèle de Translation-Synchronisation sous une une hypothèse globale de régularité. Nous proposerons deux estimateurs, le premier basé sur une approche des moindres carrés avec une pénalité traduisant la régularité, et le deuxième basé sur la projection sur l'espace des vecteurs propres de basse fréquence d'un opérateur de régularité approprié. Nous montrerons que ces deux méthodes donnent des estimateurs consistants. Nous montrerons à nouveau les performances de nos algorithmes sur des données réelles et synthétiques. Ranking and comparing arise in many real life applications, such as sports tournaments or recommendation systems. In these domains, datasets are composed of pairwise comparisons between a collection of items that can also be summarized into a comparison graph. Many parametric statistical models for ranking were introduced, such as the Bradley-Terry-Luce model, where the items are supposed to have a latent strength. The ranking are then derived from this strengths. Numerous estimation algorithms have been analyzed over the past decades, for example the maximum-likelihood or the spectral method. However, most of them do not account for the temporal aspect of the data. Indeed, ranking and personal preferences can evolve over time. In order to include temporality, we will consider a sequence of comparison graphs, or dynamic graphs, that gathers data at different time instances.We will first study an extension of the BTL model to this dynamic setting, introduced by Bong et al. under a local Lipschitz assumption on the strengths. Our algorithm is based on a nearest-neighbor approach and on the Rank Centrality algorithm, a classic estimation method in the static case. We will show [dollar]ell_2[dollar] and [dollar]ell_infty[dollar] bounds for our estimator and show our algorithm performance on both synthetic and real data.In a second part, we will introduce a dynamic version of the Translation-Synchronization model under a global smoothness assumption. We will propose two estimators, one based on a smoothness-penalized least squares approach and the other based on projection onto the low frequency eigenspace of a suitable smoothness operator. We will show that both method give consistent estimators. We also display the performance of our algorithms on synthetic and real datasets. Electronic Thesis or Dissertation Text en PDF 2020442 https://pepite-depot.univ-lille.fr/LIBRE/EDMADIS/2024/2024ULILB008.pdf http://www.theses.fr/2024ULILB008/abes https://theses.hal.science/tel-04767337 https://theses.hal.science/tel-04767337 https://theses.hal.science/tel-04767337 https://theses.hal.science/tel-04767337 https://theses.hal.science/tel-04767337 https://theses.hal.science/tel-04767337 Karlé Eglantine Karlé 1997-09-27 FR 281251037 https://theses.fr/2024ULILB008 2024ULILB008 https://doi.org/10.70675/cba87166zf713z4565z85ffz8df2faab0a39 2024-05-16 Mathématiques et leurs interactions Université de Lille (2022-....) 259265152 Doctorat Docteur es non oui Preda Cristian MADS_DIRECTEUR_DE_THESE_1 116377046 Tyagi Hemant MADS_DIRECTEUR_DE_THESE_2 26916863X Patilea Valentin MADS_PRESIDENT_DU_JURY 120380366 Maïda Mylène MADS_MEMBRE_DU_JURY_1 200109774 Marteau Clément MADS_RAPPORTEUR_1 123916119 Keribin Christine MADS_RAPPORTEUR_2 155283049 École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) MADS_ECOLE_DOCTORALE_1 631 258621362 Centre Inria de l'Université de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 104752 185432247 Laboratoire Paul Painlevé MADS_PARTENAIRE_DE_RECHERCHE_2 32 161603971 ddc:510 Preda Cristian Tyagi Hemant Patilea Valentin Maïda Mylène Marteau Clément Keribin Christine École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) Centre Inria de l'Université de Lille Laboratoire Paul Painlevé (Villeneuve d'Ascq (Nord)) PDF 2020442