Gérer et analyser les grands graphes des entités nommées - Thèses de l'INSA Lyon Accéder directement au contenu
Thèse Année : 2019

Manage and analyze large graphs of named entities

Gérer et analyser les grands graphes des entités nommées

Jocelyn Bernard

Résumé

In this thesis we will study graph problems. We will study theoretical problems in pattern research and applied problems in information diffusion. We propose two theoretical studies on the identification/detection and enumeration of dense subgraphs, such as cliques and quasi-cliques. Then we propose an applied study on the propagation of information in a named entities graph. First, we will study the identification/detection of cliques in compressed graphs. The MCE problems (for Maximal Clique Enumeration) and MCP (for Maximum Clique Problem) are problems that are encountered in the analysis of data graphs. These problem are difficult to solve (NP-Hard for MCE and NP-Complete for MCP), and adapted solutions must be found for large graphs. We propose to solve these problems by working on a compressed version of the initial graph. We show the correct results obtained by our method for the enumeration of maximal cliques on compressed graphs. Secondly, we will study the enumeration of maximal quasi-cliques. We propose a distributed algorithm that enumerates the set of maximal quasi-cliques of the graph. We show that this algorithm lists the set of maximal quasi-cliques of the graph. We also propose a heuristic that lists a set of quasi-cliques more quickly. We show the interest of enumerating these quasi-cliques by an evaluation of relations by looking at the co-occurrence of nodes in the set of enumerated quasi-cliques. Finally, we work on the event diffusion in a named entities graph. Many models exist to simulate diffusion problems of rumors or diseases in social networks and bankruptcies in banking networks. We address the issue of significant events diffusion in heterogeneous networks, representing a global economic environment. We propose a diffusion problem, called infection classification problem, which consists to dertemine which entities are concerned by an event. To solve this problem we propose two models inspired by the linear threshold model to which we add different features. Finally, we test and validate our models on a set of events.
Dans cette thèse nous étudierons des problématiques de graphes. Nous allons étudier des problématiques théoriques en recherche de motifs (patterns) et des problématiques appliquées en diffusion d'informations. Nous proposons deux études théoriques sur la recherche et l'énumération de sous-graphes denses que sont les cliques et quasi-cliques. Ensuite nous proposons une étude appliquée sur la propagation d'information dans un graphe d'entités nommées. Dans un premier temps, nous allons étudier la recherche de cliques dans des graphes compressés. Les problèmes MCE (pour l'anglais Maximal Clique Enumeration) et MCP (pour l'anglais Maximum Clique Problem) sont des problèmes rencontrés dans l'analyse des graphes de données. Ce sont des problèmes difficiles (NP-difficile pour MCE et NP-Complet pour MCP) pour lesquels des solutions adaptées doivent être conçues pour les grands graphes. Nous proposons de répondre à ces problèmes en travaillant sur une version compressée du graphe initial. Nous montrons les bons résultats obtenus par notre méthode pour l'énumération de cliques maximales sur des graphes compressés. Dans un second temps, nous étudierons l'énumération de quasi-cliques maximales. Nous proposons un algorithme distribué qui énumère l'ensemble des quasi-cliques maximales du graphe. Nous démontrons que cet algorithme liste l'ensemble des quasi-cliques maximales du graphe. Nous proposons également une heuristique qui liste un ensemble de quasi-cliques plus rapidement. Nous montrons l'intérêt de l'énumération de ces quasi-cliques par une évaluation des relations en regardant la co-occurrence des noeuds dans l'ensemble des quasi-cliques énumérées. Dans un troisième temps, nous travaillerons sur la diffusion d'événements dans un graphe d'entités nommées. De nombreux modèles existent pour simuler des problèmes de diffusion de rumeurs ou de maladies dans des réseaux sociaux ainsi que des problèmes de propagation de faillites dans les milieux bancaires. Nous proposons de répondre au problème de diffusion d'événements marquant dans des réseaux hétérogènes représentant un environnement économique du monde. Nous proposons un problème de diffusion, nommé problème de classification de l'infection, qui consiste à déterminer quelles entités sont concernées par un événement. Pour résoudre ce problème, nous proposons deux modèles inspirés du modèle de seuil linéaire auxquels nous ajoutons différentes fonctionnalités. Finalement, nous testons et validons nos modèles sur un ensemble d'événements.
Fichier principal
Vignette du fichier
Papier.pdf (6.92 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

tel-02155008 , version 1 (13-06-2019)
tel-02155008 , version 2 (29-01-2020)

Identifiants

  • HAL Id : tel-02155008 , version 1

Citer

Jocelyn Bernard. Gérer et analyser les grands graphes des entités nommées. Mathématique discrète [cs.DM]. Université Claude Bernard Lyon 1, 2019. Français. ⟨NNT : ⟩. ⟨tel-02155008v1⟩
299 Consultations
364 Téléchargements

Partager

Gmail Facebook X LinkedIn More