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

[3] https://scikit-network.readthedocs.io