رئاسـة البـحث : Lionel TABOURIER
تأطـير مـشـترك : Clémence Magnien

Ordering nodes to scale to large real-world networks

Networks are prevalent in various real-world situations such as the internet, trade, and scientific citations. As these networks grow larger, fast and scalable graph algorithms are needed to handle them. One key technique for achieving this is node ordering, where nodes are arranged based on certain properties like degree or centrality.

This approach has been adopted by state-of-the-art methods for a range of graph problems including cache optimisation, compression, and pattern mining.

This thesis presents novel contributions that leverage node ordering. First, we analyse the complexity of a triangle listing algorithm and propose new node orderings that reduce it and accelerate the listing process. Second, we show how simple orderings can improve guarantees for vertex cover without compromising scalability.

مناقـشـة مـذكـرة : 06/07/2023

أعـضاء لجنة المناقـشة :

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

إصدارات 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”, أطروحة, مناقـشـة مـذكـرة 06/07/2023, رئاسـة البـحث Tabourier, Lionel, تأطـير مـشـترك : 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)