Direction de recherche : Lionel TABOURIER
Co-encadrement : Clémence Magnien

Ordonner les nœuds pour passer à l'échelle sur les grands graphes réels

Les graphes peuvent décrire de nombreuses situations du monde réel telles que le réseau internet, les échanges commerciaux et les citations scientifiques. La taille des graphes disponibles augmente rapidement, ce qui nécessite des algorithmes rapides et qui passent à l'échelle.

Pour atteindre ce but, l'une des techniques clefs est d'ordonner les nœuds en fonction de certaines propriétés, telles que le degré ou la centralité. Cette approche est utilisée dans les méthodes les plus performantes pour plusieurs problèmes liés aux graphes : la gestion de la mémoire cache, la compression ou la recherche de motifs.

Cette thèse présente de nouvelles contributions basées sur l'ordre des nœuds. Tout d'abord, nous analysons la complexité d'un algorithme de listage de triangles et proposons de nouveaux ordres qui la réduisent et accélèrent le processus de listage. Ensuite, nous montrons comment des ordres simples peuvent améliorer les garanties de couverture par sommets sans compromettre la rapidité.

Soutenance : 06/07/2023

Membres du jury :

Laurent Viennot, Directeur de recherches INRIA, IRIF Paris Cité [Rapporteur]
Marco Bressan, Maître de conférences, Université de Milan [Rapporteur]
Claire Hanen, Professeure des universités, LIP6
David Coudert, Directeur de recherches INRIA, Sophia
Rémy Cazabet, Maître de conférences, LIRIS, Lyon 1
Clémence Magnien, Directrice de recherches CNRS, LIP6
Lionel Tabourier, Maître de conférences, LIP6

Publications 2021-2024

• 2024
  • Ch. Singh, L. Tupikina, F. Lécuyer, M. Starnini, M. Santolini : “Charting mobility patterns in the scientific knowledge landscape”, EPJ Data Science, vol. 13 (1), pp. 12, (EDP Sciences) (2024)
• 2023
  • F. Lécuyer : “Ordering nodes to scale to large real-world networks”, soutenance de thèse, soutenance 06/07/2023, direction de recherche Tabourier, Lionel, co-encadrement : Clémence, Magnien (2023)
  • F. Lécuyer, L. Jachiet, C. Magnien, L. Tabourier : “Tailored vertex ordering for faster triangle listing in large graphs”, Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), Florence, Italy (2023)
• 2021
  • F. Lécuyer, M. Danisch, L. Tabourier : “[Re] Speedup Graph Processing by Graph Ordering”, The ReScience journal, vol. 7 (1), pp. #3, (GitHub) (2021)