Xiaomin Wang

Mardi 13 décembre 2011 à 10h – salle 25-26 / 105

The degree distribution of the Internet topology is considered as one of its main properties. However, it is only known through a measurement procedure which gives a biased estimate. This measurement may in first approximation be modeled by a BFS (Breadth-First Search) tree. We explore here our ability to infer the type (Poisson or power-law) of the degree distribution from such a limited knowledge. We design procedures which estimate the degree distribution of a graph from a BFS or multi-BFS trees, and show experimentally (on models and real-world data) that our approaches succeed in making the difference between Poisson and power-law degree distribution and in some cases can also estimate the number of links. In addition, we establish a method, which is a diminishing urn, to analyze the procedure of the queue. We analyze the profile of the BFS tree from a random graph with a given degree distribution. The expected number of nodes and the expected number of invisible links at each level of BFS tree are two main results that we obtain. Using these informations, we propose two new methodologies to decide on the type of the underlying graph.

Olivier Lespinet

Jeudi 1er Décembre 2011, 11h, Amphi Herpin (bât. Esclangon)

Les champignons possèdent une très grande variété d’enzymes aux nombreuses applications potentielles. Nos travaux visent à étudier l’ensemble de cette diversité enzymatique afin de comprendre comment elle a pu prendre place et se maintenir au cours du temps. En utilisant des méthodes d’apprentissage et de fouille de données nous essayons également de voir dans quelle mesure la capacité enzymatique des champignons permet de rendre compte de leur évolution.

Bruno Pinaud

Jeudi 17 Novembre 2011, 11h, salle 25-26/105

Les systèmes de réécriture de graphes sont simples à expliquer : ils réalisent des modifications sur un graphe en remplaçant des sous-graphes sélectionnés au préalable sur la base de règles de transformations. Néanmoins, la combinaison des règles pour leur application transforme l’étude de ces systèmes en un problème complexe. A cause de cela, les experts de ces systèmes se satisfont bien souvent de représentations textuelles ou alors de dessins fait à la main pour représenter les règles de transformations. Au cours de cet exposé, je présenterai PORGY qui est un environnement visuel et interactif pour la réécriture de graphe. Cet environnement conçu avec des experts de réécritures de graphes qui avaient envie d’un véritable système interactif et visuel permet de construire, simuler et raisonner de façon visuelle et interactive sur le système complexe à étudier.

Telmo Menezes

Jeudi 17 Novembre 2011, 11h, salle 25-26/105

Complex networks are a powerful abstraction that fits a variety of phenomena across several scientific fields, including biology, sociology and economy. Analyzing and extracting insights from large complex networks is an ongoing goal of Complexity Science. In this presentation we present a novel approach based on evolutionary computation and genetic programming. Our method relies on using simple computer programs to represent network generative models, and then applying evolutionary search to find the best generators for observed networks. The final goal of this work is to be able to map large complex networks to plausible generators that have an high explanatory power. For this approach to be successful, a few obstacles have to be overcome. One of these is the measure of quality that guides evolutionary search, which has high overlap with another open problem in network theory: how to measure the distance between large networks with arbitrary sizes and topologies. We present our own solution to this problem using centrality metrics and a well known image recognition algorithm.

Thomas Aynaud

Jeudi 29 Septembre 2011, 11h, salle 26-00/101

Dans la plupart des graphes de terrain, il existe des groupes de noeuds fortement liés entre eux mais peu à l’extérieur, appelés des communautés et leur identification est importante dans de nombreux contextes pour décrire la structure du graphe. Nous étudierons la détection de ces communautés dans le cas de graphes dynamiques. Premièrement, nous détecterons des communautés à chaque instant, ce qui pose des problèmes de stabilité. Ensuite, nous définirons des communautés pertinentes sur une longue durée et proposerons une méthode pour trouver les durées intéressantes. Nous verrons enfin des applications à la détection d’événements et à la segmentation de vidéos.

Marie-Aude Aufaure

16 juin 2011 à 11h : salle 25-26/101

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.

Binh-Minh Bui-Xuan

7 avril 2011 à 11h : salle 25-26/101

Decomposition is a technical term that, from an algorithmic point of view, refers to the act of dividing an input instance into simpler pieces. Popular examples of decomposition include Merge-Sort and the factorization of polynomials. Decomposition is fundamental for divide-and-conquer algorithms, and variants such as dynamic programming. We first present a generic approach to design efficient decomposition algorithms on graphs, that will be expressed under the light of combinatorial optimisation over set famillies. We show how to apply the machinery on several old and new notions of decomposition. These decomposition notions can be extended so that NP-complete graph problems can be tackled within a reasonable (parameterized) runtime. To this aim we discuss on what can be qualified as two natural ways to generalise a particularly classical notion, the modular decomposition of graphs. One is tightly bound to a well-known topic in algorithmic graph theory called width parameters. The other links to recent works in clustering, social networks, complex systems, etc.