Conférences invitées

Conférenciers :

- Marton Karsai (Laboratoire de l'Informatique du Parallélisme, ENS de Lyon - LIP, IXXI, chaire INRIA)

Titre : Modelling temporal social networks and ongoing contagion processes

Résumé : In the last ten years the access to high resolution datasets from mobile devices, communication, and pervasive technologies has propelled a wealth of developments in the analysis of social networks. Particular efforts have been devoted to characterise how their structure influences the critical behaviour of dynamical processes evolving on top of them. However, the large majority of the approaches put forth to tackle this subject utilise a time-aggregated representation of the interactions and neglect their time-varying nature. Indeed, the concurrency, and time ordering of interactions, even if the social network contains stable relationships, are crucial and may have considerable effects.

In this talk we will discuss an activity-driven temporal network model and its variants to study the effect of time-varying interactions and various social mechanisms on the spreading of contagion processes. The model integrates key mechanisms that drive the formation and maintenance of social ties – like memory, social reinforcement, focal closure and cyclic closure, which have been shown to give rise to weight heterogeneities, community structure, weight-topology correlations, and small-world connectedness in social networks. In addition, we discuss control strategies devised for time-varying networks co-evolving with contagion processes. We derive the critical immunisation threshold and assess the effectiveness of three different control strategies. We compare the emerging characteristics of the proposed temporal model network with a real-world time-varying network of mobile phone communication, and through data-driven simulations we validate the effects of different social mechanisms and intervention strategies on contagion processes.

References: M. Karsai, N. Perra and A. Vespignani, Time varying networks and the weakness of strong ties. Scientific Reports 4, 4001 (2014). S. Liu, N. Perra, M. Karsai and A. Vespignani, Controlling Contagion Processes in Time-Varying Networks. Phys. Rev. Lett. 112, 118702 (2014) G. Laurent, J. Saramäki, M. Karsai, From calls to communities: a model for time varying social networks. arXiv:1506.00393 (submitted)

- Michel Habib, LIAFA (Laboratoire d'Informatique Algorithmique: Fondements et Applications, Université Paris Diderot)

      Titre : Graph search a nice tool to design exact and approximation algorithms for huge graphs

      Résumé : Graph Search, a mechanism for systematically visiting the vertices and edges of a graph, has been a fundamental technique in the design of graph algorithms since the early days of computer science. Many of the early search based algorithms were based on Breadth First Search (BFS) and Depth First Search (DFS) and resulted in efficient algorithms for practical problems such as distance and diameter determination, connectivity, network flows and the recognition of planar graphs. I will present two recent applications I worked on. First for the computation of the diameter of huge graphs. In a second part I will present a general framework for graph search on cocomparability graphs with application to biology to understand the structure of read networks.

- Rushed Kanawati (Laboratoire d'Informatique de Paris-Nord, Université Paris 13)
      Tutoriel sur les réseaux Multiplexes

- Mauro Sozio, Telecom Paristech, Institut Mines-Telecom Paris

Titre : Maintenir des sous-graphes les plus denses dans un graphe dynamique

      Résumé : Les algorithmes pour trouver des sous-graphes les plus denses représentent des sous-routines efficaces pour l'analyse de réseaux sociaux, notamment, pour la détection de communautés et des événement intéressants. Les réseaux sociaux comme Facebook et Twitter contiennent une grande quantité de données qui changent rapidement au fil du temps. Cela demande d'adapter les algorithmes développés pour analyser des données statiques en un environnement dynamique. Nous présentons des algorithmes efficaces pour trouver des sous-graphes les plus denses en un graphe dynamique et discutons comment nous pouvons les utiliser pour trouver des événements intéressants d'une façon automatique. Nous montrons des résultats théoriques qui sont complétés par une évaluation expérimentale sur une grande quantité de données dynamiques.