Pour la 17eme édition de la conférence, nous aurons le plaisir d’accueillir Yvonne-Anne Pignolet et Marc Lelarge pour nous parler de leur travaux de recherche au cours des deux keynotes de la conférence.
Dr. Sc. ETH Zürich
researcher at ABB Corporate Research, Switzerland
Modeling relations and networks by graphs gives access to an immensely useful set of tools. Graph theory provides the basis for understanding the functional structures of problems, as well as for powerful algorithms and their analysis, with a wide range of applications. Relations between graphs can be viewed themselves as graphs as well and thus their analysis can also benefit from these tools. In this talk we investigate the graph of graphs, where the set of nodes comprises all labelled graphs and two nodes are adjacent if the edge sets of the corresponding graphs differ by exactly one edge. This graph of graph exhibits many intriguing properties and provides a different view on dynamic networks which can be seen as paths on the graph of graphs. Assigning costs to the edges of the graph of graphs allows us to define similarity measures which lend themselves to temporal graph analysis. We demonstrate how these new tools can be exploited on six real-world networks and discuss the insights gained from them.
leader de l’équipe-projet DYOGENE, département informatique de l’ENS.
Motivated by the analysis of social networks, we study a model of random networks that has both a given degree distribution and a tunable clustering coefficient. We consider two types of growth processes on these graphs: diffusion and symmetric threshold model. The diffusion process is inspired from epidemic models. It is characterized by an infection probability, each neighbor transmitting the epidemic independently. In the symmetric threshold process, the interactions are still local but the propagation rule is governed by a threshold (that might vary among the different nodes). An interesting example of symmetric threshold process is the contagion process, 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 paper, we are able to analyze the impact of clustering on the growth processes. While clustering inhibits the diffusion process, 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.
For both diffusion and symmetric threshold models, we characterize conditions under which global cascades are possible and compute their size explicitly, as a function of the degree distribution and the clustering coefficient. Our results are applied to regular or power-law graphs with exponential cutoff and shed new light on the impact of clustering.
joint work with Emilie Coupechoux