We are interested in all aspects of real world networks and their models, from internet measurements to random graphs, from social network analysis to spreading phenomena, and from graph algorithms to biological networks.
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
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
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
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
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
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
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
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
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.
Pierre Borgnat
04 mars 2010
Dans un but de classification du trafic émis par des ordinateurs via internet mais aussi de détection des anomalies de trafic, une méthode de caractérisation des communications d’ordinateurs est étudiée. Un espace de représentation des motifs de connexions de chaque ordinateur est étudié en ce qu’il représente le trafic échangé, la dispersion de ce trafic, la connectivité de l’ordinateur. On montrera que cette représentation permet par exemple de quantifier plus finement les graphlets empiriques utilisés par la méthode BLINC (Karagiannis et al. 2005). Cette représentation du trafic échangé permet alors de mettre en place une classification non supervisée du trafic internet par une approches de classification par MST (Minimum Spanning Tree), sur des liens backbones et sans disposer du contenu des paquets ni du trafic bidirectionnel (ici validé sur le trafic backbone d’un lien transpacifique opéré par WIDE, Japon).
Marc Lelarge
25 février 2010
Nous introduisons un modèle de diffusion qui généralise à la fois le processus de contact et la percolation ‘bootstrap’. Nous analysons ce processus sur des graphes aléatoires dilués. Ceci nous permet de retrouver des résultats connus (taille de la composante géante, seuil de percolation) et nouveaux (condition de cascade, impact de différentes vaccinations). Les preuves reposent sur des idées de couplages développées récemment par Janson et Luczak.
Jean-Baptiste Rouquier
28 janvier 2010
In many networks, vertices have hidden attributes that are correlated with the networks topology. For instance, in social networks, people are more likely to be friends if they are demographically similar. In food webs, predators typically eat prey of lower body mass. We explore a setting in which the networks topology is known, but these attributes are not. If each vertex can be queried, learning the value of its hidden attributes but only at some cost then we need an algorithm which chooses which vertex to query next, in order to learn as much as possible about the attributes of the remaining vertices. We assume that the network is generated by a probabilistic model, but we make no assumptions about the assortativity or disassortativity of the network. We then query the vertex with the largest mutual information between its type and that of the others (a well-known approach in active learning) or with the largest average agreement between two independent samples of the Gibbs distribution which agree on its type. We test these approaches on two networks with known attributes, the Karate Club network and a food web of species in the Weddell Sea. In several cases, we found that the average agreement algorithm performs better than mutual information, and both perform better than simpler heuristics. The algorithms appear to explore the network intelligently, first querying vertices at the centers of communities, and then vertices along the boundaries between communities.
Damien Magoni
02 février 2011 de 14h à 15h : salle 26-00/228
In order to untie entities, applications and devices, CLOAK introduces a P2P overlay architecture and redefines the notion of a session. A session is a communication descriptor that contains everything needed for linking entities, applications and devices together in a flexible way. A session represents the identity and the management information of a given communication. Thus the lifetime of a communication between several entities is equal to the lifetime of its corresponding session. A device can move or be changed for another without terminating the session. Similarly, an application can be changed for another if deemed appropriate or even moved (i.e. mobile code) also without terminating the session. Finally entities can move or change (i.e. be transferred to another entity) without terminating the session if this is appropriate for a given communication. We can see that in our new architecture, entities, applications and devices are loosely bound together during a communication and all the movements and changes of devices, applications and entities are supported. To be able to implement our notion of session, we need to introduce several new layers of identifiers in order to decouple lower layers (devices) from middle layers (entities) and from higher layers (applications). Hence the name CLOAK given to this project. We add naming layers above the existing ones in order to give abstract names to objects such as entities and devices. Thus we lay a cloak on the current Internet architecture.