Pierre Latouche

Jeudi 14 Juin 2012 à 11h, salle 26-00/101

Slides

Les réseaux sont largement utilisés en sciences sociales afin de décrire les intéractions entre individus. Dans ce contexte, de nombreuses méthodes non-supervisées de clustering ont été développées afin d’extraire des informations, à partir de la topologie des réseaux. La plupart d’entre elles partitionne les noeuds dans des classes disjointes, en fonction de leurs profils de connection. Récemment, des études ont mis en évidence les limites de ces techniques. En effet, elles ont montré qu’un grand nombre de réseaux « réels » contenaient des noeuds connus pour appartenir à plusieurs groupes simultanément. Pour répondre à ce problème, nous proposons le modèle à blocs stochastiques chevauchants, Overlapping Stochastic Block Model (OSBM) en anglais. Cette approche autorise les noeuds à appartenir à plus d’une classe et généralise le très connu Stochastic Block Model, sous certaines hypothèses. Nous proposons un algorithme d’inférence permettant de classer les nouds d’un réseau, ainsi qu’un critère de sélection de modèles pour estimer le nombre de classes. Nous utilisons ces travaux pour analyser la blogosphère politique française.

Laura Hernandez

Jeudi 24 mai 2012 à 11h, salle 25-26/101

Mutualistic ecosystems are usually groups of animals and plants, helping each other to fulfil essential biological functions such as feeding or reproduction as in seed dispersal or pollination networks. Such systems may be described in terms of a complex network, where the nodes represent the animal or plant species and the links represent the existence of a contact between a plant and an animal species. As only contacts between nodes belonging to different guilds are allowed, the corresponding network is bipartite. Coding this information in a bipartite adjacency matrix, it is observed that real ecosystems are not a random collection of interacting species, but they display instead, a high degree of internal organization. Different hypothesis are discussed in the ecological literature to explain this particular order. It is fairly obvious that a detailed explanation of the interaction behaviour of individual species can be of little help to understand the generalized pattern that is found across ecological systems of very different sizes and types, that involve plants of different nature and animals that range from insects to birds. The tools commonly used by ecologists to study these systems are based on the statistical analysis of observed data. In this talk I will present an alternative way to study this problem, by introducing an algorithm that allows us to try different supposed hypothesis in the form of a Contact Preference Rule (CPR) that governs the dynamics of the system. Starting from a random configuration the system is evolved under the studied CPR and the comparison of the order state reached by this artificial system with the order observed in real systems allows us to decide whether a CPR may be considered or not as responsible for the observed order. In particular, I will introduce a new way to measure the order of mutualistic ecosystems and I will discuss about the relationship between the phylogenetic proximity of the members of each guild and the observed order.

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.