Recherche de sous-graphes denses et d'événements dans les médias sociaux

Event detection in social media is the task of finding mentions of real-world events in collections of posts. The motivation behind our work is two-folded: first, finding events that are not covered by mainstream media and second, studying the interest that users show for certain types of events. In order to solve our problem, we start from a graph based characterization of the data in which nodes represent words and edges count word co-occurrences. Density is a very good measure of importance and cohesiveness in graphs. Taking into account the special properties of real-word networks, we can develop algorithms that efficiently solve hard problems. The contributions of this thesis are: devising efficient algorithms for computing different types of dense subgraphs in real-world graphs, presenting a novel dense subgraph definition and providing an efficient graph-based algorithm for event detection.La détection d’événements dans les réseaux sociaux consiste à retrouver les traces d’événements réels dans des flux d’informations en ligne. L’ambition de notre travail est double : trouver, dans un premier temps, des événements que les principaux médias ne traitent pas et, dans un second temps, étudier l’intérêt que les utilisateurs ont pour certains types d’événements. Pour résoudre notre problème nous commençons par une caractérisation des données basée sur un graphe dans lequel les noeuds sont des mots et les arêtes représentent le nombre de cooccurrences. La densité est une très bonne mesure de l’importance et de la cohésion dans les graphes. En prenant en compte les propriétés caractéristiques des réseaux du réel, nous pouvons développer des algorithmes capables de résoudre efficacement des problèmes complexes. Les contributions de cette thèse sont : concevoir des algorithmes efficaces pour calculer différents types de sous-graphes denses dans des graphes réels, et fournir un algorithme orienté graphe efficace pour la détection d’événements