Fouille de Données dans les Réseaux Sociaux et d’Information : Dynamiques et Applications

Networks (or graphs) have become ubiquitous as data from diverse disciplines can naturally be mapped to graph structures. The problem of extracting meaningful information from large scale graph data in an efficient and effective way has become crucial and challenging with several important applications and towards this end, graph mining and analysis methods constitute prominent tools. This dissertation contributes models, tools and observations to problems that arise in the area of mining social and information networks. We built upon computationally efficient graph mining methods in order to: (i) design models for analyzing the structure and dynamics of real-world networks towards unraveling properties that can further be used in practical applications; (ii) develop algorithmic tools for large-scale analytics on data with inherent (e.g., social networks) or without inherent (e.g., text) graph structure. In particular, for the former point we show how to model the engagement dynamics of large social networks and how to assess their vulnerability with respect to user departures from the network. In both cases, by unraveling the dynamics of real social networks, regularities and patterns about their structure and formation can be identified; such knowledge can further be used in various applications including churn prediction, anomaly detection and building robust social networking systems. For the latter, we examine how to identify influential users in complex networks, having direct applications to epidemic control and viral marketing and how to utilize graph mining techniques in order to enhance text analytics tasks and in particular the one of text categorization.Les réseaux (ou graphes) sont devenus omniprésents en raison de leur capacité à représenter naturellement les données trouvées dans de nombreuses et diverses disciplines. Extraire efficacement des informations pertinentes de graphes à grande échelle est un problème crucial et difficile ayant de nombreuses applications. À cette fin, les méthodes de fouille de données graphiques constituent des outils importants. Par l’introduction de nouveaux modèles et outils, et par la réalisation d’observations, cette thèse contribue à la résolution de problèmes qui se posent dans le domaine de la fouille de données provenant des réseaux sociaux et d'information. Nous utilisons des méthodes efficaces de fouille de données graphiques afin de: (i) concevoir des modèles pour l'analyse structurelle et dynamique des réseaux réels dans le but d’extraire des connaissances pouvant être utilisées en pratique, (ii) développer des outils algorithmiques pour l'analyse à grande échelle de données intrinsèquement graphiques (par exemple, réseaux sociaux) ou non intrinsèquement graphiques (par exemple, le texte). En particulier, pour le premier point, nous montrons comment modéliser la dynamique d'engagement au sein de grands réseaux sociaux et comment évaluer leur vulnérabilité par rapport aux départs des utilisateurs. Dans les deux cas, en mettant à jour la dynamique de réseaux sociaux réels, nous pouvons identifier des régularités et des motifs dans leur structure et leur formation. De telles connaissances trouvent de nombreuses applications comme la prévision du churn, la détection des anomalies et la construction de systèmes de réseautage robustes. Dans le deuxième point, nous nous concentrons sur l’identification des utilisateurs influents dans les réseaux complexes, avec des applications directes sur le contrôle des épidémies et le marketing viral, et sur l’utilisation de techniques de fouille de données graphiques pour améliorer les tâches d'analyse de texte et en particulier la classification du texte