Emilie Coupechoux

Lundi 2 avril 2012 à 14h, salle 55-65/211

Slides

Motivated by the analysis of social networks, we study a model of network that has both a given degree distribution and a tunable clustering coefficient. We analyze two types of epidemic processes on this random graph model: a diffusion process, which is characterized by an infection probability, each neighbor transmitting the epidemic independently, and a contagion model, which is inspired by a simple coordination game played on the network. Both types of processes have been used to model spread of new ideas, technologies, viruses or worms and results have been obtained for random graphs with no clustering. In this talk, we are interested in the impact of clustering on the growth processes. In both cases, we characterize conditions under which a global cascade is possible, and compute the cascade size explicitly, as a function of the degree distribution and the clustering coefficient. While clustering inhibits the diffusion process (in power-law and regular graphs), its impact for the contagion process is more subtle and depends on the connectivity of the graph: in a low connectivity regime, clustering also inhibits the contagion, while in a high connectivity regime, clustering favors the appearance of global cascades but reduces their size.

Camille Roth

Vendredi 2 mars 2012 à 14h, salle 25/26-101

Slides

Subway networks shape, to some extent, the structure of movements of individuals across a city; similarly, they are being partially shaped by the presence of these individuals in the city. This talk will present two complementary studies describing the dynamic processes which subway networks both host and undergo. The first analysis focuses on dynamics processes occurring on the subway network of a large city (London) in terms of its commuting patterns. It uses the large scale, real-time electronic ticketing data from the Oyster Card system, introduced less than a decade ago, to reveal a part of the structure and organization of the city. More precisely, this study shows that patterns of intraurban movement are strongly heterogeneous in terms of volume, but not in terms of distance travelled, and that there is a polycentric structure composed of large flows organized around a limited number of activity centers. For smaller flows, the pattern of connections becomes richer and more complex and is not strictly hierarchical since it mixes different levels consisting of different orders of magnitude. The second study investigates the temporal evolution of the major subway networks in the world over the last century. The main result is that most of these networks tend to converge to a shape which shares some generic features, despite their geographical and economical differences. These features include a core with branches radiating from it to cover about twice the average radial extension of the core. The core generally includes about 60% of the network stations and exhibits an average degree of order 2.5. Interestingly, core and branches define two distinct and universal regimes in terms of the number of stations at a given distance from the barycenter. This result which was difficult to interpret in the framework of fractal geometry finds here a natural explanation. More broadly, these two types of studies open the way to more integrated analyses of the coevolution between the dynamics on and of subway networks.

Blaise Ngonmang

Jeudi 22 mars 2012 à 11h, salle 25-26/101

Slides

In social networks, the detection of communities has gained considerable interest because it can be used for instance for visualization, recommendation in business applications or the analysis of the spread of infectious diseases. Many methods proposed in the litera- ture for the solution of this problem, assume that the structure of the entire network is known, which is not realistic for very large and dynamic networks. For this reason, approaches have been introduced recently to find the local community of a node. Most of these methods often fail when the starting node is at the boundary of a community. In addition, they are not able to detect overlapping communities. In this work, we propose new methods to find local communities that don’t have these drawbacks. Experiences on real and computer generated social networks such as Netscience, Amazon 2006 and Lan- cichinetti et al.’s benchmark show that these methods perform better than the solutions with which the comparisons were performed.

Renaud Lambiotte

Jeudi 16 février 2012 à 11h – salle 55-65/211

Slides

In this talk, I will present recent results from 2 recent papers. i) Random teleportation is a necessary evil for ranking and clustering directed networks based on random walks. Teleportation enables ergodic solutions, but the solutions must necessarily depend on the exact implementation and parametrization of the teleportation. For example, in the commonly used PageRank algorithm, the teleportation rate must trade off a heavily biased solution with a uniform solution. Here we show that teleportation to links rather than nodes enables a much smoother trade-off and effectively more robust results. We also show that, by not recording the teleportation steps of the random walker, we can further reduce the effect of teleportation with dramatic effects on clustering. ii) The traditional way of studying temporal networks is to aggregate the dynamics of the edges to create a static weighted network. This implicitly assumes that the edges are governed by Poisson processes, which is not typically the case in empirical temporal networks. Consequently, we examine the effects of non-Poisson inter-event statistics on the dynamics of edges, and we apply the concept of a generalized master equation to the study of continuous-time random walks on networks. We show that the equation reduces to the standard rate equations when the underlying process is Poisson and that the stationary solution is determined by an effective transition matrix whose leading eigenvector is easy to calculate. We discuss the implications of our work for dynamical processes on temporal networks and for the construction of network diagnostics that take into account their nontrivial stochastic nature.

Jean-Charles Delvenne

Lundi 6 février 2012 à 11h – salle 25-26/105

Dynamical systems taking place on networks, such as opinion dynamics, synchronization, consensus or random walks, reveal a lot about their structure. In particular we show, through a dynamical reinterpretation of well-known concepts, how centrality measures (such as pagerank, eigencentrality, etc.) and community detection quality functions (such as modularity, Potts, model, stability, etc.) are intimately related. The dynamical interpretation allows to design new centrality or community detection measures tailored for every particular application.

Arnaud Legout

Mardi 31 janvier 2012 à 11h – salle 25-26/101

Slides

In this presentation, we show how to exploit real-time communication applications to determine the IP address of a targeted user. We focus our study on Skype, although other real-time communication applications may have similar privacy issues. We first design a scheme that calls an identified-targeted user inconspicuously to find his IP address, which can be done even if he is behind a NAT. By calling the user periodically, we can then observe the mobility of the user. We show how to scale the scheme to observe the mobility patterns of tens of thousands of users. We also consider the linkability threat, in which the identified user is linked to his Internet usage. We illustrate this threat by combining Skype and BitTorrent to show that it is possible to determine the filesharing usage of identified users. We devise a scheme based on the identification field of the IP datagrams to verify with high accuracy whether the identified user is participating in specific torrents. We conclude that any Internet user can leverage Skype, and potentially other real-time communication systems, to observe the mobility and filesharing usage of tens of millions of identified users.

Hervé Rivano

Vendredi 20 janvier 2012 – salle 203-205 (bât 41)

Slides

Les réseaux radio maillés sont une solution d’extension des infrastructures cellulaires. Ils permettent de densifier simplement le réseau en collectant le trafic d’utilisateurs vers un point d’accès à l’infrastructure via des communications radio multi-saut. Cette densification permet une diminution des puissances d’émission, donc des consommations énergétiques, et un accroissement de la capacité offerte aux utilisateurs. Durant ce séminaire, nous présenterons des formulation en programmation linéaire et génération de colonnes de l’optimisation du routage et de la configuration de tels réseaux et nous en servons pour étudier le compromis entre consommation énergétique du système et capacité du réseau sur des modèles au réalisme croissant. Nous concluons sur les perspectives d’une étude prenant en compte de manière détaillée l’environnement urbain dans lequel ces réseaux ont vocation à être déployés.

Eric Freyssinet

Jeudi 5 janvier 2012 à 11h – salle 25-26 / 101

Slides

Présentation générale des activités contre la cybercriminalité de la gendarmerie nationale. Projet de recherche sur le cas spécifique des botnets.

Thomas Aynaud

Mercredi 30 novembre 2011 à 14h en salle 25-26 / 105

La plupart des graphes de terrain ont une structure particulière constituée de communautés. Les noeuds sont organisés suivant des groupes appelés des communautés avec beaucoup de connexions internes mais peu entre eux. L’identification des communautés apporte un éclairage nouveau sur la structure du graphe et est importante dans de nombreux contextes. Elle a, par exemple, déjà été utilisée pour la visualisation de graphes et pour étudier différents types de réseaux comme des réseaux sociaux ou biologiques. Nous allons étudier cette structure dans le cas des réseaux dynamiques. Pour cela, nous allons suivre deux approches. La première consiste à suivre des communautés au cours du temps en les détectant à chaque instant et en suivant leur évolution. Nous verrons que bien que très naturelle, cette approche pose de nombreuses questions de stabilité : les algorithmes ont tendance à modifier beaucoup leur résultat même si le réseau change peu. Cela implique que les transformations observées dans les communautés sont en fait liées à l’algorithme et non à l’évolution de la structure du réseau. Nous proposerons donc une analyse de l’instabilité de trois algorithmes et une solution que nous validerons sur plusieurs graphes de terrain. La deuxième approche consiste à détecter la structure communautaire non pas juste pour un instant mais pour une période donnée appelée la fenêtre de temps. La durée de la période est alors un problème crucial et nous proposons une méthode de décomposition en fenêtres de temps dans un graphe dynamique. Une particularité de la méthode est que le résultat est un regroupement hiérarchique : les fenêtres de temps sont elles-mêmes susceptibles d’en contenir. En outre, les fenêtres n’ont pas besoin d’être contiguës ce qui permet par exemple de détecter une structure se répétant. Enfin, nous conclurons par des applications à la détection d’événements sur Internet et la segmentation de vidéos. Nous montrerons que l’on peut détecter des événements en trouvant les moments où la structure change brutalement et montrerons que nous détectons à la fois de nouveaux événements et des événements déjà identifiés par d’autres méthodes. Pour la segmentation de vidéos, nous avons aussi eu des problème de stabilité et nous avons donc développé une méthode plus stable de suivi et de détection.

Lamia Benamara

Mardi 29 novembre 2011 à 11h, en salle 25-26 / 105

Les graphes de terrain apparaissent dans de nombreux contextes : réseaux informatiques, réseaux biologiques, réseaux sociaux, graphes issus du web, etc. Jusqu’à récemment ces objets étaient principalement étudiés sous un angle statique. Or, la plupart de ces graphes sont en réalité des graphes dynamiques. Cette dynamique peut apparaître d’une façon différente selon les contextes : réseaux sociaux dans lesquels des connexions entre individus apparaissent et disparaissent au cours du temps, graphes du web dans lesquels des pages sont créées ou supprimées, etc. Un grand nombre de résultats de ces 10 dernières années ont introduit un ensemble d’outils pour l’analyse et la description des graphes statiques, mais peu a été fait pour l’étude de leur dynamique. Nous avons abordé dans cette thèse la problématique de la caractérisation de la dynamique des graphes de terrain tout en prenant en compte le biais lié à la mesure, en nous appuyant sur des cas concrets de graphes dynamiques. Nos contributions se sont orientées dans deux directions. Nous nous somme tout d’abord intéressés à l’étude du biais dans l’observation de la dynamique induit par le fait que la période d’observation est finie. Nous avons proposé une nouvelle méthodologie qui permet de déterminer si la longueur de la période d’observation est suffisante pour une caractérisation rigoureuse d’une propriété donnée. Cette méthodologie est générique et peut être appliquée à n’importe quelle propriété caractérisant un graphe de terrain dynamique. Pour démontrer la pertinence de notre méthodologie, nous l’avons appliquée à l’étude de différentes propriétés dans un système P2P. Notre deuxième contribution consiste en une approche pour étudier des graphes dynamiques. Nous avons cherché à la fois à caractériser la dynamique globale de ces systèmes, et à identifier les éventuels nœuds ayant un comportement particulier. Nous avons étudié plusieurs jeux de données issus de réseaux de contacts entre personnes et nous avons montré que chaque jeu de données a ses particularités. Nous avons également constaté que certaines caractéristiques sont partagées par tous les jeux de données. En particulier, la dynamique globale du réseau change en fonction de la période d’observation et le comportement de certains nœuds diffère du comportement global du système.

Abdelhamid Salah Brahim

Jeudi 8 décembre 2011 à 10h30 – salle 25-26 / 105

On peut modéliser de nombreux objets issus du monde réel par des graphes. Ces objets sont issus de contextes très différents (ex. réseaux informatiques, sociaux ou biologiques), cependant ils se ressemblent au sens de certaines propriétées statistiques. On les désigne sous le terme général de graphes de terrain (complex networks en anglais) ou grands graphes d’interaction. L’analyse des graphes de terrain est probablement le plus grand champ de recherche du domaine et l’étude des phénomènes de diffusion constitue un des axes importants dans la compréhension de ces objets. Beaucoupde précédentes études ont été menées sur la diffusion avec une approche théorique mais avec l’apparition de données issues du monde réel de plus en plus riches, une approche empirique de l’analyse de ces réseaux est apparue comme une nécessité. La diffusion peut être de différentes natures: diffusion d’information, d’idées ou d’opinion. Cette diffusion est vue dans la plupart des travaux comme le résultat de l’interaction entre les éléments du réseau (i.e. les nœuds du graphe). En complément de cette vision, nous considérons dans cette thèse que la diffusion, en plus de se produire entre les nœuds, est aussi le résultat de l’interaction entre des groupes de nœuds, appelés communautés, qui ont des propriétés en commun. On dit que le réseau possède une structure en communautés. Cette approche ouvre de nouvelles perspectives pour la compréhension et la caractérisation des graphes de terrain. L’objectif de cette thèse est d’étudier les phénomènes de diffusion de manière empirique non seulement à l’échelle des nœud mais à différents niveaux de la structure en communautés. A l’aide d’une approche statistique, nous proposons un ensemble de méthodes et de métriques pour aborder la diffusion sous un nouvel angle et aller plus loin dans la caractérisation de ces phénomènes .Nous nous proposons d’étudier les liens de diffusion au sein d’un réseau de blogs francophones. Nous montrons en premier lieu l’impact des communautés sur la popularité des blogs et distinguons des classes de comportement. Cela nous conduit à investiguer les interactions entre les communautés. Pour ce faire, nous définissons deux mesures: la distance communautaire et l’Homophilie. En dernier lieu, nous étudions la diffusion de proche on proche dans le graphe, caractérisée par des cascades de diffusion. Nous montrons que notre approche permet de détecter et d’interpréter les différents comportements de diffusion et de faire le lien entre les propriétés topologiques, temporelles et communautaires.

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.

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.