Encadrants :
Occurrences :
Nombre d'étudiants minimum:
Nombre d'étudiants maximum:
Nombre d'instances :
Domaines:
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 computation-heavy). 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 scikit-network [3] library. This would involve testing those algorithms on real-world large-scale data.
Project
The tasks for this proposal include:
-
familiarising with the scikit-network 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