Encadrants :
Occurrences :
Nombre d'étudiants minimum:
Nombre d'étudiants maximum:
Nombre d'instances :
Domaines:
Faisable à distance:
Context
Drawing a graph is a very open question, dependent on specific needs of the user. However, a variety of algorithms exist to produce a nice layout for any graph just from its nodes and edges. Many rely on physical models (for instance placing springs between the nodes of a graph with stiffness based on the corresponding edge weights) and make simulations to find that model's equilibrium position which yields a layout.
Algorithm [1]
Force Atlas 2 is a popular layout algorithm which uses a combination of tricks to ease the computation needed to simulate the model (in particular the repulsive force between nodes which is computationheavy). It can also be used to produce an embedding of the nodes of a graph (that is it associates each node with a vector) in any dimension (for a layout this dimension is 2 or 3).
This makes it possible to get a layout for very large graphs efficiently.
Application
Any working algorithm could be included in the scikitnetwork [3] library. This would involve testing those algorithms on realworld largescale data.
Project
The tasks for this proposal include:

familiarising with the scikitnetwork API

implementing the Force Atlas 2 algorithm[1, 2] for graph layout

testing the algorithm on relevant data
The reference language is Python, with emphasis on the SciPy and NumPy libraries.
References
[1] https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0098679
[2] https://github.com/bhargavchippada/forceatlas2/blob/master/fa2/forceatlas2.py