Description
Date depot: 3 avril 2020
Titre: Sorting Nodes to Scale to Massive Real-World Networks
Directeur de thèse:
Lionel TABOURIER (LIP6)
Directrice de thèse:
Clémence MAGNIEN (LIP6)
Domaine scientifique: Sciences pour l'ingénieur
Thématique CNRS : Non defini
Resumé:
Real datasets are here the motivation to build new theoretical tools that specifically adapt to them. That is the approach taken by the Complex Networks team of the LIP6 in the LiMass project (Linear algorithms for Massive real-world graphs) . The PhD project is supervised by members of this team. Additionally, regular visits to the CRI Paris (Center for Research and Interdisciplinarity) are planned, where the Network Ties team collects and analyses data from various sources.
Sorting the nodes of an input graph in a relevant order has proved to be a key subroutine for solving many problems in massive graphs. Such order-dependent algorithms are particularly interesting to develop efficient algorithms, as the relevant order of the nodes can generally be computed in quasi-linear time.
For instance, the degree ordering can be obtained by first computing the degree of each node (time O(m + n)) and then sorting them. We can do that in time O(n.log(n)) with quick sort, or even O(n) using bucket sort, as degrees are bounded by n. Similarly, the degeneracy ordering has become one of the most popular node ordering; it can be obtained in linear time by repeatedly removing a node of minimal degree (graph pealing algorithm).
Examples of problems benefiting from sorting nodes in a relevant order include finding a dense subgraph, listing triangles, listing k-cliques, finding or listing maximal cliques, counting k-motifs and compressing graphs.
The PhD candidate will work on (i) finding better orders to use in existing order-dependent graph algorithms, (ii) suggesting new efficient order-dependent graph algorithms and (iii) applying these tools to several large real-world networks (both well-known and newly-collected datasets).
Doctorant.e: Lécuyer Fabrice