Aline Carneiro Viana

Lundi 14 mai 2012 à 11h, salle 25-26/101

Slides

The constant advancement of information systems has allowed more data to be generated and stored from the most diverse situations. It is fascinating that, behind these records, we see the reflection of the environment itself, since every record represents a decision made by some entity. In this work, we modeled real-world scenarios of mobility from using temporal complex networks. The analysis assumes that these systems are composed of entities able to interact in a rational manner, reflecting their interests and activity dynamic. In this direction, we propose a technique for analyzing mobility scenarios from random graphs. This technique examines how the real system would evolve if the agents decisions were random, and from there, you can check, for example, which edges are random and which are derived from social relationships, such as friendship or professional.

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.