"Spring" Details

[AndrewLawrence]

Hi, thanks for the excellent package!

This is a request for information on the spring layout method and potentially to add this info to the documentation.

Initialisation

Spring layout is the Fruchterman Reingold method, but the FR algorithm in the '91 paper starts with a random initialisation of node positions. The "spring" layout in qgraph gives the same result each time which from the code seems to be because qgraph generates a fixed initialisation.

The current igraph implementation of fr (layout_with_fr) gives a different result each time unless you set.seed.

The qgraph() documentation says:

A solution to use this function for weighted graphs has been taken from the igraph package (Csardi G & Nepusz T, 2006) in which the same function was ported from the SNA package.

Igraph has had some updates, did it diverge since the function was modified for qgraph? Or was the deterministic behaviour added for qgraph?

Weight scaling

The weights used in the call to the qgraph FR algorithm are normalised weight / max(weight) and then squared (unless sig = TRUE). This diverges from igraph, and I don't think is documented? (apologies if I'm missing this).

I think the end result (graph layouts) in qgraph look great, and the deterministic behaviour is really desirable, but it would be great to clarify the deterministic behaviour and weight scaling points somewhere in the R docs.

[SachaEpskamp]

Hi!

The initialization is by placing the nodes on a circle. I have added some rounding options too since to improve the deterministic behavior even more. Psychologists don't like random results (there is even a paper saying the layout doesn't replicate... even though it is a chaotic algorithm...). A very long time ago I described this all in a draft for https://www.jstatsoft.org/article/view/v048i04, but reviewers wanted me to omit it because they thought the algorithm was described in enough detail already...

I will look into updating the documentation at some point. Indeed the function is based on an older igraph implementation originally, with weights set to 1/abs(normalized weight). There are some options for constraining the displacement of nodes too that are pretty poorly documented at the moment..,

[AndrewLawrence]

Thanks, that's great. As I say the end result is very nice. I came across the above when trying to replicate qgraph's layout in another package for tweaking purposes.

The circle initialisation sounds like the initialisation in Kamada Kawai.

If you don't mind another question, after initialization there is another non-deterministic part of the FR algorithm: a random perturbation when node positions are tied for one or more dimensions in the repulsive step. Is this random perturbation removed, or somehow made deterministic? (Apologies, my C/C++ is not good and I can't tell for certain from source code)

[SachaEpskamp]

I don't know about this extra step? The qgraph algorithm is always in two dimensions. Every iteration it simply computes the sum of repulsion and attraction for every node and moves the nodes accordingly.

Best, Sacha

[AndrewLawrence]

Sorry I described that badly. I mean what happens if mid-algorithm two nodes end up with tied x,y coordinates?

I can see that qgraph.layout.fruchtermanreingold() perturbs randomly if the initial placement has ties.

This is the line governing the random repulsion in igraph's implementation: layout_fr.c#L92

In the FR'91 paper they say:

A special case occurs when vertices are in the same position: our implementation acts as though the two vertices are a small distance apart in a randomly chosen orientation: this leads to a violent repulsive effect separating them.

[SachaEpskamp]

Ah, this special case is not handled in qgraph at the moment... You just end up with the nodes overlapping each other.