Actualités du LIPN

Orateur:

Nous accueillerons Alain Gely de l’Équipe Algorithmique et Optimisation du Laboratoire d’Informatique Théorique et Appliquée de l’Université Paul Verlaine de Metz.

Résumé:

Dans cet exposé, on revient sur quelques algorithmes d’énumération des ensembles fermés.
Après un détour par le problème de l’énumération des cliques maximales d’un graphe, on montre qu’il s’agit en fait d’instances de parcours d’un graphe fortement connexe : le graphe de transition. En se servant de cet outil comme moyen de comparaison des algorithmes, on remarque que Next-Closure, en particulier, est une transcription directe au problème d’énumération des fermés de l’algorithme d’énumération des cliques maximales du à Tsukiyama et Al.

Éric Mermet présentera ses travaux le 2 décembre à 14h15 dans la salle de séminaires LITIS/LMAH à UFR ST du Havre

Un réseau de transport repose sur la trame d’un système spatial dont le rôle est de mettre en relation des lieux sur un territoire. C’est aussi un objet géographique complexe qui peut être étudié de plusieurs façons. Une analyse dite thématique ou fonctionnelle permet d’extraire de nombreuses informations (enquêtes ménage déplacement, études de flux migratoires, etc.) mais demande un accès, souvent difficile, à des données hétérogènes. Une analyse structurelle, si elle ne substitue pas à une analyse thématique, permet néanmoins de dégager de l’information et notamment la part investie par le réseau dans la compréhension d’un phénomène. Elle repose sur la construction et l’analyse d’indicateurs basés sur les relations proposées par le réseau et ne demande donc pas d’avoir accès à des données particulières. Ces indicateurs relationnels, comme la centralité, l’accessibilité, les chemins de contournement locaux, etc., permettent d’expliciter en quoi la structure, l’organisation spatiale et topologique des composantes du réseau prédisposent à la mise en relation plus ou moins aisée de lieux de l’espace. Or, ce type d’analyse engendre trois complexités :

  - une complexité combinatoire liée au nombre de relations Origine-Destination existantes sur le réseau,
   - une complexité algorithmique liée aux calculs mathématiques des indicateurs,
   - et une complexité visuelle liée à la mise en valeur d’informations pertinentes par une cartographie aisément compréhensible.

Le modèle proposé dans cette thèse vise à contrôler les complexités décrites et, in fine, à faciliter l’analyse de la structure d’un réseau aux utilisateurs (urbanistes, gestionnaires de réseaux, aménageurs, chercheurs). Cette analyse repose sur la création de cartes exploratoires ciblées et donc liées à un phénomène particulier que l’on cherche à analyser. Pour cela, un langage graphique informatique a été mis en place dans lequel il est possible de combiner visuellement ces cartes à l’aide de différents opérateurs. L’analyse n’est alors plus linéaire mais devient arborescente, rapprochant ce raisonnement du processus de pensée de l’utilisateur. Ces aspects ont été développés dans un outil logiciel baptisé GeoGraphLab.

Les réseaux sociaux, informatiques ou biologiques sont composés d’éléments connectés les uns aux autres et constituent des réseaux d’interaction réels, également appelés graphes de terrain (ou complex networks en anglais).. L’analyse de ces réseaux d’interaction est extrêmement complexe, du fait de leur taille, de leur grand nombre de dimensions et du manque de connaissance de leur structure. Durant cette présentation, je présenterai une méthode d’analyse exploratoire de ces réseaux, reposant sur l’analyse formelle de concepts et les treillis de Galois en particulier. Ces outils permettent d’identifier la structure (en communautés) de ces réseaux; je montrerai comment visualiser cette structure, et comment l’exploiter pour mieux comprendre les réseaux étudiés. La question du passage à l’échelle d’une telle approche sera également abordée.

Business Intelligence aims at supporting better business decision-making, by providing tools and methods for collecting, modeling and interacting with data. Users have to deal with big data from structured databases and unstructured content (emails, documents, social networks, etc). Moreover, these data are often distributed and highly dynamic. Social Media and mobile technologies have changed our way to access information, facilitating communication and data exchange/sharing. All these evolutions refer to Business Intelligence 2.0.

An adapted modeling and visualization technique of links and interactions between several objects (e.g. products and sites, customers and products, social network...) is a precious mean to permit a good understanding of a lot of situations in the enterprise context. In this latter context, most of the time, these objects and their relations are stored in relational databases. But extracting and modeling such heterogeneous graphs, with heterogeneous objects and relations, are outside of the classical graph models capabilities, moreover when each node contains a set of values. On the other hand, graph models can be a natural way to present these interactions and to facilitate their querying. In this way, we propose a graph model named SPIDER-Graph which is adapted to represent interactions between complex heterogeneous objects extracted from relational databases, used for heterogeneous objects graph extraction from a relational database. One of the steps involved in this approach consists in identifying automatically the enterprise objects. Since the enterprise ontology has been used for describing enterprise objects and processes, we propose to integrate it in the object identification process (identify objects to be able to transform a graph of heterogeneous objects according to the user choice). Finally, we introduce the main principles of an aggregation algorithm used for community detection and graph visualization.