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.

Franck Ghitalla

19 mai 2011 à 11h : salle 25-26/101

Au delà des graphes et des méthodes de leur visualisation, la cartographie de l’information représente un univers original qui a ses propres contraintes. L’exposé sera l’occasion de présenter les principales dimensions de la cartographie d’information, à partir d’exemples commentés.

Jean-Daniel Fekete

24 février 2011 à 11h : salle 25-26/101

Slides

Les réseaux sont des objets complexes qui peuvent être analysés et explorés, généralement à laide de visualisation. Jusquà présent, la grande majorité des outils de visualisation utilise la représentation par nœuds et liens : les sommets sont représentés par des nœuds et les arcs par des lignes. Cette représentation est familière mais elle devient illisible lorsque le réseau devient dense. Alternativement, il est possible dafficher la matrice dadjacence du réseau en plaçant les sommets en lignes et colonnes et les liens en cellules à lintersection de ces lignes et colonnes. Une cellule est marquée lorsquun arc existe entre le somme de la ligne et celui de la colonne. Cette représentation est moins familière mais reste lisible même lorsque la densité du réseau augmente. Ces dernières années, la représentation matricielle a été beaucoup étudiée : nous allons présenter les divers solutions proposées pour visualiser, ordonner et naviguer dans ces matrices dadjacence, ainsi que les représentations mélangeant matrices avec nœuds et liens.

Mario Chavez

27 janvier 2011

Slides

Electroencephalography, magnetoencephalography, or functional magnetic resonance imaging (fMRI) techniques are currently used to estimate functional connectivity patterns between different brain areas. In this talk I’ll show how a complex network description might provide new insights into the understanding of human brain connectivity during different pathological and cognitive neuro-dynamical states.

Laurent Viennot

16 décembre 2010

Slides

tant donné un graphe G, un spanner est un sous graphe H qui couvre tous les sommets de G. On s’intéresse alors à deux paramètres : la distance dans H par rapport à la distance dans G, et la taille de H en nombre d’arêtes. L’optimisation simultanée de ces deux paramètres conduit à des compromis que nous mettrons en évidence.

Juan David Cruz-Gomez

03 décembre 2010

Slides

Classic algorithms for community detection in social networks use the structural information to identify groups in the social network, i.e., how clusters are formed according to the topology of the relationships. However, these methods don’t take into account any semantic information which could guide the clustering process, and which may add elements to do further analyses. The method we propose, uses in a conjoint way, the semantic information from the social network, represented by the point of view, and its structural information. This is, by the combination of the relationships, expressed by the edges on one hand, and the implicit relations deduced from the semantic information on the other hand.

Dmitri Krioukov

07 juillet 2010

We establish a connection between the scale-free topology of complex networks, and the hyperbolic geometry of hidden metric spaces underlying these networks. Given a hyperbolic space, networks topologies with scale-free degree distributions and strong clustering naturally emerge on top of the space as topological reflections of its hyperbolic geometry. Conversely, for any scale-free network with strong clustering, there is an effective hyperbolic space underlying the network. The underlying hyperbolic geometry enables greedy routing with optimal efficiency. Greedy routing does not require any global information about network topology to navigate the network. At each hop, greedy routing selects as the next hop the current hop neighbor closest to the destination in the underlying hyperbolic space. We show that in complex networks mapped to their hyperbolic spaces, greedy routing always succeeds reaching the destination, following the topologically shortest paths. Furthermore, we show that even without re-mapping the network or changing any node coordinates, this navigation efficiency is remarkably robust with respect to rapid network dynamics, and catastrophic levels of network damage. We map the real Internet AS-level topology to its hyperbolic space, and find that greedy routing using this map exhibits similar efficiency. These results effectively deliver a solution for Internet interdomain routing with theoretically best possible scaling properties. Not only routing table sizes and stretch are as small as possible, but also routing communication overhead is reduced to zero.

Shaowen Qin

17 juin 2010

We present a study on clustering of software classes based on software execution data, which offers a dynamic, hence more realistic, perspective to the understanding of software structure and the evaluation and improvement of the existing architectural design. The approach first uses association rule mining to extract low-level class relations in object-oriented software. The mining results are then processed by hypergraph-based clustering to identify an optimal set of high-level clusters of classes that have relatively high cohesion within and low coupling between them. It is also shown that such clusters are actually unique. The identified clusters can be seen as execution components of the software, which represents the effect, rather than the intention of the existing design. Two case studies are presented to demonstrate the application of our approach. Relevant concepts in complex network are also introduced to interpret the findings of this study

Jussara Almeida

10 juin 2010

A number of online video social networks, out of which YouTube is the most popular, provides features that allow users to post a video as a response to a discussion topic. These features open opportunities] for users to introduce polluted content into the system. For instance, spammers may post an unrelated video as response to a popular one aiming at increasing the likelihood of the response being viewed by a larger number of users. Moreover, opportunistic users – promoters – may try to gain visibility to a specific video by posting a large number of (potentially unrelated) responses to boost the rank of the responded video, making it appear in the top lists maintained by the system. In this talk, I will present some of our initial results on detecting spammers and content promoters on YouTube. Our study is based on a characterization of several properties associated with YouTube users as well as the use of state-of-the-art classification algorithms.

Alina Stoica

10 juin 2010

Slides

Pour le développement des services ou le marketing, la connaissance des utilisateurs (des plateformes sociales en ligne, du téléphone mobile, fixe etc.) est très importante. Pour améliorer cette connaissance, on peut analyser les usages, collecter des données socio-démographiques ou étudier les réseaux sociaux modélisant les relations entre les utilisateurs. Dans cet exposé je présenterai une méthode permettant de caractériser chaque individu en utilisant le réseau social auquel il est connecté. Après avoir obtenu une caractérisation de chaque personne, on peut alors mesurer les corrélations avec d’autres indicateurs liés à l’individu. Je présenterai la comparaison de cette caractérisation prenant en compte le réseau social avec des indicateurs de popularité en ligne sur MySpace et de fréquence de communication par téléphone mobile.

Etienne Birmelé

25 mai 2010

Slides

Une approche classique d’analyse statistique des réseaux biologiques est de déterminer les motifs de ces réseaux, c’est-à-dire les sous-graphes dont le nombre d’occurrences dans le réseau est significativement plus élevé que dans un modèle aléatoire, l’idée directrice étant que leur présence en sur-nombre indique une sélection positive au cours de l’évolution. Cependant, les méthodes existantes se réfèrent à une sur-représentation dans l’ensemble du graphe alors qu’il est connu que les motifs ayant un intérêt biologique ont tendance à s’agglomérer en certaines régions du graphe. Je définirai la notion de motif local et développerai les trois aspects que nécessite leur détection: le modèle de réseaux aléatoires sous-jacent le problème de comptage du nombre d’occurences d’un sous-graphe dans un réseau la mise au point d’une statistique permettant de décider si un sous-graphe est sur-représenté Enfin, je développerai l’application de la méthode au réseau de régulation de la levure.

Marie-Noelle Comin

29 avril 2010

Slides

Cities concentrate economic activities, information, power and people in both quantitative and qualitative ways. Cities are also nodes of networks of complex interconnection. In Europe, the construction of a large supranational entity results spatially in the multiplication and the intensification of the relations between politically unified countries. The majority of these relations pass through cities. Then very complex links underpin the European system of cities and understanding them is critical to understanding the interdependencies in the system. In this talk, the interconnection of the European national urban systems is studied by analysing knowledge spillovers which flow between the European cities. Knowledge spillovers are considered as an input and also an output of the innovation process. For the analysis, I consider networks created by collaborative research in European funded research and technology development projects dedicated to converging technologies. Data come from the EC database CORDIS RTD-PROJECTS drawn from the 2nd to the 6th European Framework Programmes (1986 to 2006). Cities concentrate economic activities, information, power and people in both quantitative and qualitative ways. Cities are also nodes of networks of complex interconnection. In Europe, the construction of a large supranational entity results spatially in the multiplication and the intensification of the relations between politically unified countries. The majority of these relations pass through cities. Then very complex links underpin the European system of cities and understanding them is critical to understanding the interdependencies in the system. In this talk, the interconnection of the European national urban systems is studied by analysing knowledge spillovers which flow between the European cities. Knowledge spillovers are considered as an input and also an output of the innovation process. For the analysis, I consider networks created by collaborative research in European funded research and technology development projects dedicated to converging technologies. Data come from the EC database CORDIS RTD-PROJECTS drawn from the 2nd to the 6th European Framework Programmes (1986 to 2006).

Hoàng Anh Phan

15 avril 2010

Le paradigme pair-à-pair (ou P2P, pour peer-to-peer) soppose au paradigme client-serveur . Dans un système pair-à-pair dont les utilisateurs partagent un ensemble de ressources, telles que des fichiers ou des ressources de calcul, tous jouent le même rôle. En particulier, chaque utilisateur peut agir comme serveur pour certains pairs, et comme client pour dautres. Plusieurs méthodes de publication et de recherche de ressources ont été proposées pour les systèmes P2P. Parmi ces propositions, les tables de hachage distribuées (ou DHT, pour Distributed Hash Table) se basent sur un plongement des ressources et des utilisateurs dans un même espace métrique, appelé espace des clés. Cette espace possède une structure permettant le routage, sur lequel peut construire les fonctions de publications et de recherches. En effet, les réseaux P2P peuvent être utilisés comme support de diffusion multimédia. La fonctionnalité de multicast nayant pas encore été déployée à grande échelle dans lInternet au niveau IP, plusieurs propositions visent à promouvoir le déploiement de procédures de multicast au niveau applicatif, par exemple dans un réseau logique P2P. Je parlerai dans un premier temps de la mise en marche du protocole P2P D2B : gestion de la dynamicité du réseau, des joints et départs en même temps, de la tolérance aux pannes. Ensuite, je présenterai de trois méthodes déquilibrage de charge dans les réseaux P2P basés sur les graphes de De Bruijn. Enfin, je décrirai un algorithme multicast: Tree-Farm, basés sur lensemble des arbres nÅ“uds intérieurs disjoints. Nous avons montré que, dans le cas des systèmes P2P utilisant la topologie des graphes de De Bruijn, Tree-Farm atteignait une meilleure bande passante (pour un taux de perte nul) que lalgorithme BFS utilisant un seul arbre multicast enraciné en la source ou que lalgorithme PrefixStream [L. Viennot et A. T. Gai – ICON2006]. Le paradigme pair-à-pair (ou P2P, pour peer-to-peer) soppose au paradigme client-serveur . Dans un système pair-à-pair dont les utilisateurs partagent un ensemble de ressources, telles que des fichiers ou des ressources de calcul, tous jouent le même rôle. En particulier, chaque utilisateur peut agir comme serveur pour certains pairs, et comme client pour dautres. Plusieurs méthodes de publication et de recherche de ressources ont été proposées pour les systèmes P2P. Parmi ces propositions, les tables de hachage distribuées (ou DHT, pour Distributed Hash Table) se basent sur un plongement des ressources et des utilisateurs dans un même espace métrique, appelé espace des clés. Cette espace possède une structure permettant le routage, sur lequel peut construire les fonctions de publications et de recherches. En effet, les réseaux P2P peuvent être utilisés comme support de diffusion multimédia. La fonctionnalité de multicast nayant pas encore été déployée à grande échelle dans lInternet au niveau IP, plusieurs propositions visent à promouvoir le déploiement de procédures de multicast au niveau applicatif, par exemple dans un réseau logique P2P. Je parlerai dans un premier temps de la mise en marche du protocole P2P D2B : gestion de la dynamicité du réseau, des joints et départs en même temps, de la tolérance aux pannes. Ensuite, je présenterai de trois méthodes déquilibrage de charge dans les réseaux P2P basés sur les graphes de De Bruijn. Enfin, je décrirai un algorithme multicast: Tree-Farm, basés sur lensemble des arbres nÅ“uds intérieurs disjoints. Nous avons montré que, dans le cas des systèmes P2P utilisant la topologie des graphes de De Bruijn, Tree-Farm atteignait une meilleure bande passante (pour un taux de perte nul) que lalgorithme BFS utilisant un seul arbre multicast enraciné en la source ou que lalgorithme PrefixStream [L. Viennot et A. T. Gai – ICON2006].

Monojit Choudhury

09 avril 2010

One of the very important aspect of studying any complex network is to characterize and describe its global structure, which, by definition, is too complex to be described in terms of simple statistics. Traditionally aggregate statistics of certain local properties, such as degree distribution, assortatitivity, and clustering coefficient are used to characterize the topology of the network, but these statistics do not capture the global structure of a network. In this talk, I shall describe how the spectrum of a network (i.e., the eigenvalues and eigenvectors of the adjacency matrix of the network or its Laplacian) provides us with valuable insight into the global structure of the network and therefore, the underlying physical processes generating it. I will take the following three case studies from the domain of language to illustrate this: (a) the co-occurrence networks of words, (b) the networks of syntactic and semantic similarity of the distribution of words, and (c) the co-occurrence network of phonemes (PhoNet).

Marc Barthelemy

08 avril 2010

Most transportation networks are embedded in space and consequently, their topology is not independent from spatial constraints. In particular, these constraints can induce a hierarchical organization with hubs controlling specific regions of space, non-trivial correlations between the weights, the connectivity pattern and the actual spatial distances of vertices, and the emergence of anomalous fluctuations in the betweenness-degree correlation function. In this talk I will illustrate these effects both from an empirical and modeling point of view, with various examples ranging from the large scale air travel network to smaller scales of inter- and intra- cities transportation networks.

Mathieu Bastian

25 mars 2010

In this practical talk, I will present 0.7 version of Gephi, open-source graph visualization & manipulation software. Gephi possesses a complete set of network visualization and analysis features, proposes major innovations in dynamic and hierarchical graphs and above all is a flexible and extensible architecture for plugins. I will firstly sum up embedded features: Layout, Metrics, Ranking, Filters, Partition, Preview, Clustering, DataLab. Then, I will present and discuss dynamic and hierarchical graphs features and roadmaps while showing live demo. Afterwards, I will outline our approach by presenting the Gephi project, some insights about performance and the various possibilities of using and extending Gephi in the way scientists and engineers can rely on. To conclude I will speak about plugin development and show how to create a plugin in five minutes.

Jean-Jacques Pansiot

11 mars 2010

Slides

Active and passive measurements for topology discovery have known an impressive growth during the last decade. If a lot of work has been done regarding inter-domain topology discovery and modeling, only a few papers raise the question of how to extract intra-domain topologies from measurements results. In this paper, based on a large dataset collected with mrinfo, a multicast tool that silently discovers all interfaces of a router, we provide a mechanism for retrieving intra-domain topologies. The main challenge is to assign an AS number to a border router whose IP addresses are not mapped to the same AS. Our algorithm is based on probabilistic and empirical IP allocation rules. The goal of our pool of rules is to converge to a consistent router to AS mapping. We show that our router-to-AS algorithm results in a mapping in more than 99% of the cases. Furthermore, with mrinfo, point-to-point links between routers can be distinguished from multiple links attached to a switch, providing an accurate view of the collected topologies. Finally, we provide a set of large intra-domain topologies in various formats.