Direction de recherche : Matthieu LATAPY

Co-encadrement : TARISSAN Fabien

Phénomènes de diffusion sur les grands réseaux : mesure et analyse pour la modélisation

Dans cette thèse, nous avons étudié la diffusion de l’information dans les grands graphes de terrain (des réseaux d’interaction complexes réels), en se focalisant par- ticulièrement sur les patterns structurels de la propagation. Plus précisément, notre objet d’étude central est la cascade de diffusion, c’est-à-dire, le graphe qui relie les nœuds du réseau (qui représentent des individus, machines, etc) par où l’information est passée, en mettant en évidence “qui a transmis l’information à qui”. Cet objet topologiquement riche a reçu beaucoup d’attention depuis quelques années grâce à la disponibilité de traces numériques détaillées sur des événements de diffusion en ligne (email, fichiers, tweets, etc.). Sur le plan empirique, il s’est avéré difficile de capturer la structure des cascades de diffusion en termes de mesures simples. Diverses propriétés des cascades ont été étudiées, mais on n’a pas encore trouvé un ensemble de propriétés simples permettant de synthétiser la structure des cascades. Sur le plan théorique, l’approche classique consiste à étudier des modèles stochastiques de contagion et de percolation sur des graphes aléatoires ou réguliers. Le traitement analytique de ce type de modèle sur des structures discrètes s’avère difficile, mais malgré la complexité, plusieurs résultats concernant le comportement asymptotique de modèles simples sont apparus dans la littérature. Néanmoins, le champ d’application de ces modèles reste limité, car les cascades réelles ont généralement une topologie complexe et le processus de diffusion se produit dans une fenêtre de temps limitée (généralement pas assez grande pour l’analyse asymptotique). Par conséquent, une meilleure compréhen- sion des données empiriques, des modèles théoriques et du lien entre les deux est également cruciale pour la caractérisation de la diffusion dans les grands graphes de terrain.
Ce document est organisé de la manière suivante : nous commençons, au pre- mier chapitre, par un état de l’art sur les graphes de terrain et la diffusion dans ce contexte. Dans le chapitre 2, nous décrivons notre jeu de données et discutons sa pertinence dans le contexte du premier chapitre. Nous présentons la procédure de reconstruction du graphe sous-jacent (où se passe la diffusion) et des cascades de diffusion. Ensuite, dans le chapitre 3, nous évaluons la pertinence d’un des modèles classiques de diffusion sur les réseaux : le modèle SIR. Nous examinons également quelques extensions de ce modèle qui prennent en compte des hétérogénéités de notre jeu de données, ainsi qu’un raffinement du processus de reconstruction du graphe d’intérêt. Dans le chapitre 4, nous explorons la prise en compte du temps dans l’évolution du réseau sous-jacent et dans le modèle de diffusion. Dans le chapitre 5, nous évaluons l’impact de la structure du graphe sous-jacent sur la structure des cascades de diffusion générées avec les modèles étudiés dans les chapitres précédents. Nous terminons ce document par un bilan des résultats (que nous résumons dans la suite) et des perspectives ouvertes par les travaux menés dans cette thèse.

Publications 2012-2019

• 2019
  • L. Tabourier, D. Bernardes, A.‑S. Libert, R. Lambiotte : “RankMerging: A supervised learning-to-rank framework to predict links in large social networks”, Machine Learning, vol. 108 (10), pp. 1729-1756, (Springer Verlag) (2019)
• 2014
  • D. Bernardes : “Information Diffusion in Complex Networks: Measurement-Based Analysis Applied to Modelling”, thèse, soutenance 21/03/2014, direction de recherche Latapy, Matthieu, co-encadrement : Tarissan, Fabien (2014)
  • R. Hollanders, D. Bernardes, B. Mitra, R. Jungers, J.‑Ch. Delvenne, F. Tarissan : “Data-driven traffic and diffusion modeling in peer-to-peer networks: A real case study”, Network Science, vol. 2 (3), pp. 341-366, (Cambridge University Press) (2014)
• 2013
  • D. Bernardes, M. Latapy, F. Tarissan : “Inadequacy of SIR Model to Reproduce Key Properties of Real-world Spreading Phenomena: Experiments on a Large-scale P2P System”, Social Network Analysis and Mining, vol. 3 (4), pp. 1195-1208, (Springer) (2013)
• 2012
  • D. Bernardes, M. Latapy, F. Tarissan : “Examining Key Properties of Diffusion Models for Large-Scale Real-World Networks”, Quatorzièmes Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (Algotel’12), La Grande Motte, France, pp. 1-4 (2012)
  • D. Bernardes, M. Latapy, F. Tarissan : “Relevance of SIR Model for Real-world Spreading Phenomena: Experiments on a Large-scale P2P System”, IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Istanbul, Turkey, pp. 327-334, (IEEE) (2012)