Graph layout service

[jamesscottbrown]

Sigma.js provides extremely limited abilities for graph layout: it has a plugin that implements the forceAtlas2 algorithm, and a plugin that arranges the nodes in a grid then repulses any nodes that overlap, but nothing else.

This means that a user who wants an alternative layout must first perform the layout initially before using the OVE Networks app.

We could address this by adding a OVE Aset Service that accepts a network and the name of layout algorithm (with values for any required parameters), and computes the layout. This could use either:

• Gephi (probably using the Gephi Toolkit, which provides a library as a single JAR file)
• Tulip (probably using the python bindings, though it can also be used as a C++ library)

[miguems]

You are right, layout computation is a "missing feature" I have pointed out several times in the past in relation with the graph app in gdofw, and its port to OVE. The network app in OVE (with the tile server and other optimizations) is merely focusing on the visualisation part. So far, graphs are assumed to have a layout with them.

However, as we described in https://doi.org/10.1016/j.future.2018.06.015 layout is indeed the biggest contributor of computational cost of processing graphs. This is made worse by the fact that these algorithms are generally tricky and costly to parallelize.

What was done in the past re. graph app in GDOfw was to precompute (manually) the layout in gephi and store the graph with coordinates in a file. Any layout change required to go back to gephi, recalculate the layout and reload the file in the app.

I believe that if we really want a compelling graph app in OVE, we need to provide some layout capabilities, and of course, they cannot be given to the sigma.js plugins (which are terrible in terms of performance). In the aforementioned paper, we implemented a simple force layout algorithm in Spark for our testing, but the service James proposes should go much further than this.

[senakafdo]

So, point is this.

If the solution was to pre-compute the layout and redo the graph, then there is nothing wrong in the way the networks app in OVE works today because that is all that you require. Sigma supports GEXF as a format and its purpose in life is to help you integrate well with Gephi's layout computation capabilities. This document, explains the whole process.

Now, whether you chose Gephi to do it, or you wrote some code to wrap that, it doesn't make any difference and Gephi will fail at some scale and your code will fail at some other scale, so technically speaking neither is a viable option. There is however a possibility to implement a solution that may work out well for a subset of all problems such as sparsification, but is not generic enough to adopt in a platform like OVE.

Also, I see no real value in wrapping an existing layout pre-computation library with another service, because it is way more convinient to write a simple script that is much more efficient compared to a standard asset service.

The use of a Graph DB OTOH makes it extremely easy for dynamic layout computations. If done right, you can serve the same data (or a variation of the data - subsets/supersets/updates) without having to recompute the graph.

Therefore, personally, I see two options:

1. Use an approach similar to what is proposed by https://doi.org/10.1016/j.future.2018.06.015 or make it possible in this asset service to change the layout computation algorithm, which may default to a few provided by Gephi (or equivalents).

2. Develop plugins that sit right above a Graph DB that can compute layouts. There are several examples of this being done before, and, https://academic.oup.com/bioinformatics/article/31/23/3868/208976 is one.

I would not discourage someone from doing exactly what is being proposed here as an alternative to exposing the graph directly to OVE. However, what I do not prefer is us coming up an Asset Service that is dedicated to serve all networks that are visualised in OVE, and that mutating the Networks App to an extent where we introduce significant performance and usability bottlenecks. This is typically why I found graphtile-v0 not very well suited.

[oserban]

This will be moved into the new AM