Supervision : Lionel TABOURIER

Co-supervision : 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.

2021-2024 Publications

• 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”, thesis, phd defence 07/06/2023, supervision Tabourier, Lionel, co-supervision : 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)