Projet de recherche doctoral numero :3628

Date depot: 1 janvier 1900
Titre: Extension de PageRank et application aux réseaux sociaux
Directeur de thèse: Fabien MATHIEU (Nokia-Bell-Labs)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini

Resumé: Contexte : A l’ère du monde numérique, l’analyse des grandes bases de données est un sujet d’actualité techniquement complexe. Savoir exploiter ces informations est essentielle et un enjeu de plus en plus important. D’une manière générale, il s’agit de transformer le web de l’information en web des connaissances, et de tirer parti de la masse d’information disponible pour produire des connaissances, des informations qui ont du sens. Un exemple typique de réussite d’une telle exploitation est l’exemple de Google avec PageRank : en 1998, Brin et Page ont lancé le moteur de recherche Google. Comparé aux compétiteurs de l’époque, comme Altavista, Google s’est démarqué par l’exploitation de l’algorithme de PageRank. PageRank est un algorithme de classement de l’importance des nœuds d’un graphe par une équation récursive convergeant vers un point fixe. L’idée générale est qu’une page est importante si elle est référencée (à travers les hyperliens) par des pages importantes. Aujourd’hui, la croissance des contenus générés par les utilisateurs (Youtube, messages postés dans les réseaux sociaux, crowd-sourcing) rend nécessaire d’avoir un système de classement qui soit à la fois très efficace et hautement personnalisable : on passe de quelques milliards de sites web à quelques dizaines/centaines de milliards de contenus/objet webs. Dans un tel contexte, nous souhaitons approfondir l’application des idées de PageRank dans un contexte étendu de données hétérogènes pour un algorithme de classement pertinent de l’importance des données. Il s’agit d’un sujet de thèse qui potentiellement recouvre des domaines très larges de recherche théorique (algèbre linéaire, analyse numérique, théorie de la probabilité, théorie de graphe, problème d’optimisation) et pratique (calcul numérique, programmation, structure de données, calcul distribué, programmation GPU). 1. Objectifs : Le but de cette thèse est de concevoir et de construire un nouveau système distribué d’analyse de contenus, à partir de plusieurs idées proposées sur le classement, la navigation et les modalités d’interactions, avec comme possible cas d’application la brique fondamentale à la base d’un nouveau moteur de recherche performant. Cela nécessite de construire ou d’importer des grandes bases de données et de comparer les solutions proposées à l’état de l’art (comme par exemples des solutions proposées basées sur mapReduce et Pregel), incluant la possibilité de développer un site web expérimental pour construire une nouvelle base de données. Être capable de construire une solution pratique est essentiel afin de valider, ou invalider, les résultats théoriques. Il sera aussi crucial de pouvoir adapter et/ou améliorer des idées existantes pour mettre au point une solution innovante. Le candidat se focalisera dans un premier temps sur l’aspect de la qualité de classement et la prise en compte du coût de calcul (algorithmique), notamment dans le contexte de calcul distribué, permettant un passage à l’échelle de très grande base de données. Puis, il faudra construire le système, en choisissant judicieusement un cas d’application concrète et précise. Nous souhaitons également à travers cette thèse, développer des codes open sources, afin de faire bénéficier à la communauté de recherche les résultats qui seront obtenus. 2. Organisation du travail La première année sera en partie consacrée à l’analyse de l’état de l’art. Ce domaine de recherche, qui a déjà donné lieu à une littérature très abondante, est très concurrentiel dans le contexte actuel de développement rapide de plateformes de réseaux sociaux. Nous démarrons néanmoins avec des atouts importants, sous la forme de résultats déjà obtenus très prometteurs, qu’il faudra faire aboutir afin que le savoir-faire se développe en France. En fait, la mise en place d’un système distribué de base de données et de calcul est un aspect fondamental pour le passage à l’échelle des techniques et pour un possible réel déploiement. Le candidat devra donc non seulement assimiler les résultats connus, mais également les résultats récents proposés par les Bell Labs, avant de se lancer dans l’apprentissage de l’architecture des systèmes distribués. Dans la seconde année, le candidat pourra approfondir les modèles existants, notamment dans le contexte de graphe hétérogène, ce qui est un sujet difficile. Il devra en même temps travailler sur l’architecture à mettre en place, qui devra être adaptée par rapport au besoin de ce projet, et développer une première solution (avec les outils tels que mapReduce ou Pregel). Dans la troisième année, le candidat devra être capable d’exploiter les outils développés pour analyser les données construites et évaluer les résultats. Le candidat pourra approfondir un des aspects suivants : - Aspect algorithmique du ranking : o Analyse de pertinence, modification, les failles etc ; o Extension au cas général ; - Aspect calcul : o Calcul parallèle et distribué, architec

Doctorant.e: Huynh The Dang