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.

Pierre Borgnat

04 mars 2010

Slides

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

Slides

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

Slides

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

Slides

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.

Marcelo Dias De Amorim

14/01/2010, de 11H00 à 12H00, en salle 847

Slides

In this talk, we will discuss some preliminary work on the spatial characterization of intermittently-connected wireless networks. The motivation is that the literature has focused almost exclusively on the temporal aspect of contacts and inter-contacts between nodes. Furthermore, it is frequently assumed that contacts have infinite capacity, which is a too strong consideration especially in wireless networks. We propose the surround indicator as a metric to exhibit the spatial dimension of contacts in opportunistic networks. This metric can be used for example as a measure of potential interference that a contact might undergo or to understand the validity of forwarding strategies like betweenness centrality. We evaluate the surround indicator on two existing datasets. Our preliminary results reveal that contacts have too heterogeneous surrounds to be considered only in terms of duration. This work is part of Nadjet Belblidia’s thesis and is done in collaboration with Jérémie Leguay (Thalès), Vania Conan (Thalès), Jon Crowcroft (Cambridge University), and Serge Fdida (UPMC).

Christophe Prieur

19/11/2009, de 11H00 à 12H00, en salle 555

Slides

En dix ans, la vision Google des réseaux sociaux a cédé la place à la vision Facebook. Dans le milieu des années 90, avec l’apparition du web et son intégration progressive dans la société, s’est répandue l’image d’un monde connecté, village global traversé par les autoroutes de l’information permettant de relier n’importe qui à n’importe qui d’autre en six degrés de séparation. En 1998, Google apportait à cette civilisation-là un algorithme permettant de traiter le gigantesque bazar que constituait déjà le graphe des pages web, permettant d’en extraire les pages les plus pertinentes pour le genre humain. Aujourd’hui, les résultats de Google sont un acquis, c’est la wikipédie de tout un chacun, presque aussi poussiéreuse que le Larousse de la grand-mère. Je sais, quand j’en ai besoin, chercher des informations dans le réseau des réseaux, reste donc à trouver des informations quand je ne les cherche pas (Google ne me dira ce qu’est Paf le chien que si j’ai l’idée de le lui demander), et pour cela, écouter ce qui se passe dans… mon réseau. Parce que si je suis à O(6) degrés de séparation de n’importe qui, je préfère réduire la portée de mon réseau pour limiter la cacophonie, et le pagerank ne m’aidera pas pour ça. Nous allons donc profiter de notre expérience de vieux googliens pour aborder les réseaux personnels avec des outils que les anciens analystes des réseaux sociaux n’avaient pas, quitte à ce qu’ils nous reprochent de leur piquer leur jouet.

Fabien de Montgolfier

12/11/2009, de 11H00 à 12H00, salle 847

Slides

La vidéo à la demande (VoD) est un service en pleine expansion. Avec le développement des modems ( box ) d’accès à l’ADSL, offrant maintenant des capacités de stockage, on peut imaginer un service totalement décentralisé. Les films sont pré-chargés sur certains modems. Les utilisateurs se connectent aux modems qui les ont pré-chargés et visionnent, sans intervention d’un serveur (d’où un service robuste et à coût faible). Nous montrons que le nombre de films disponibles peut croitre de façon linéaire (ou quasi-linéaire sous d’autres hypothèses) en fonction du nombre de modems et que toutes requêtes d’utilisateurs peuvent être satisfaites AFP. Travail réalisé avec Y. Boufkhad, F. Mathieu, D. Perino et L. Viennot.

Stefano Battiston

28 avril 2011 de 11h à 12h en salle 25-26/101

We introduce a discrete dynamics of distress propagation in networks. The formulation combines a diffusion and a contact process which are relevant to complex networks in general. In particular it is more suitable than previous models to describe contagion processes occurring in the financial system. Our results indicate that diversification of risk at the individual level can have an ambiguous effect on the global level, leading in some cases to higher systemic risk. Moreover, we show that the same structure can be resilient or fragile depending on the relative strength of the two processes at play. In the financial context, this corresponds to the level of optimism in the market. Thus, our work has interesting implications for the debate on the network architecture that is most resilient to financial crises.

Oussama Allali

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

Slides

Beaucoup de graphes de terrain, comme les relations acteur-film ou fichier-fournisseur, ont une nature bipartie et sont modélisés par des graphes bipartis, dont les nœuds sont divisés en deux ensembles avec des liens entre des nœuds de différents ensembles seulement. Cependant, il y a actuellement un manque de méthodes pour analyser correctement ces graphes, la plupart des méthodes existantes étant conçues pour des graphes classiques. Une approche courante, mais qui a des limites, consiste à transformer les graphes bipartis en graphes classique, par un procédé appelé projection. Cependant ceci entraîne une perte importante d’informations. Dans cet exposé je présenterai les liens internes et je les proposerai comme une nouvelle notion importante pour analyser les graphes de terrain bipartis : elle permet de mesurer la redondance dans ces graphes, et de mesurer la perte d’information entre un graphe biparti et ses projections. Jemontreraien étudiant différents jeux de données que les liens internes sont très fréquents, et que les statistiques associées permettent de souligner les ressemblances et les différences entre les graphes deterrainbipartis et les graphes bipartis aléatoire. La plupart des graphes de terrain sont de plus dynamiques, c’est-à-dire que leur structure évolue au fil du temps par l’ajout et/ou le retrait de nœuds et/ou de liens. L’étude de la dynamique des graphes de terrain peut s’aborder par le problème de la prédiction de nouveaux liens dans ces graphes. Plusieurs travaux ont étudié le problème de la prédiction de liens dans les graphes classiques (non-bipartis). Toutefois, leurs méthodes ne sont pas directement applicables à, ou appropriées pour, les graphes bipartis. Je présenterai une approche basée sur les liens internes pour la prédiction dans les graphes bipartis. Je montrerai que notre méthode fonctionne très bien, beaucoup mieux que l’approche de recommandation classique.

Emmanuel Lazega

17 mars 2011 de 11h à 12h : salle 25-26/101

La question de savoir si la structure dun collectif reste stable malgré un fort turnover de ses membres et un fort turnover des relations entre ces membres est une question classique de la sociologie. Nous proposons une réponse à cette question en procédant à une analyse longitudinale dun réseau de conseil intra-organisationnel explorant la relation entre la structure formelle de lorganisation et un processus dapprentissage collectif par ses membres. Nous identifions une structure centre-périphérie et un mouvement cyclique de centralisation-décentralisation du réseau de conseil. Nous expliquons cette dynamique comme leffet dune oscillation des membres de lorganisation entre surcharge et conflits épistémiques. La question de la stabilité de la structure malgré un fort turnover de ses membres et un fort turnover des relations entre eux est ainsi traduite en termes de stabilisation plus ou moins précaire de cette dynamique par les acteurs du système eux-mêmes.

Arnaud Legout

10 mars 2011 de 11h à 12h : salle 25-26/101

Les risques d’atteinte à la vie privée sur Internet sont largement sous estimés. Il est connu que les internautes laissent énormément d’informations personnelles sur, par exemple, les réseaux sociaux. Cependant, peu de gens savent que toute activité sur Internet laisse des traces. Dans cet exposé, nous allons montrer qu’il est possible de collecter ces traces à grande échelle et sans infrastructure dédiée. Plus précisément, nous allons montrer qu’il est possible de surveiller l’activité sur BitTorrent de centaines de millions d’internautes. Nous allons également montrer qu’en exploitant des mesures faites sur BitTorrent et sur un réseaux de voix sur IP, il est non seulement possible de lier à une identité réelle une liste de téléchargement de manière automatique, mais qu’il est également possible de suivre les déplacements d’un grand nombre de personnes sans que ces personnes n’aient aucun moyen de détecter ni de bloquer ces mesures.

Ludovic Denoyer

10 février 2011 de 11h à 12h : salle 25-26/101

We consider the problem of labeling nodes in a multi-graph where the nodes may be connected with different types of relations. This type of problem occurs in many situations like for example the analysis of social networks or bibliographic data. Relations may be provided (e.g. friends) or computed (e.g. similarity). We propose a new learning algorithm for exploiting the rich multi-relational information in the labeling task. This method is able to optimally learn combining the influence of different relation types. It is one of the very first algorithms able to handle multi-graph information for this classi fication task. We describe experiments on four datasets which show the model ability to deal with complex relationships and to take bene fit of multi-relational information for complex labeling problems.