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

Jocelyn Bernard 1
1 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : 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.
Document type :
Complete list of metadatas

Cited literature [169 references]  Display  Hide  Download

Contributor : Jocelyn Bernard <>
Submitted on : Thursday, June 13, 2019 - 11:49:15 AM
Last modification on : Saturday, June 15, 2019 - 1:34:02 AM


Files produced by the author(s)


  • HAL Id : tel-02155008, version 1


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. ⟨tel-02155008⟩



Record views


Files downloads