Inverted edge weigh in layout algorithms (e.g. ForceAtlas2,...)

[vlado-s]

Current Behavior

Currently the interpretation of the edge weight (W) in Gephi (or at least in the ForceAtlas2 layout algorithm) is such, that higher W is interpreted as "stronger connection" and is reflected also in the thickness of the line representing the edge. However other algorithms often interpret W in a inverse fashion, where W is the cost/penalty for "going through" the edge, e.g. when searching for shortest paths (notably the NetworkX routines). Neither way is right or wrong - it is more a "philosophical" question which interpretation will be canonical. But this discrepancy results in some counter-intuitive consequences, such as e.g. when I obtain the shortest path from NetworkX and look at it in Gephi (after node distribution with ForceAtlas2), then it passes through distant nodes connected by thin lines.

It would be therefore beneficial to include an option that would make it possible to obtain a graph layout with the inverse interpretation of W.

Expected Behavior

The expected behaviour would be such, that nodes connected via edges with smaller W would have stronger attraction than those with larger W. Also the line thickness should be inverted to current state.

Possible Solution

I have discussed this (via e-mail) with Mathieu Jacomy, who confirmed the above mentioned interpretation. He suggested that I may create a pull. However, I’m afraid I’m not confident enough to modify someone’s else’s code and resume responsibility for it working correctly. There are however two simple solutions for addressing this issue that come to mind:

1. Use the inverse of W in the calculation of the attractive force between connected nodes (eq. 6 in the ForceAtlas2 paper, https://doi.org/10.1371/journal.pone.0098679). So F_attr ~ 1/W. Here also the display of the edge (line thickness) would have to be modded.

2. Rescale all W in such way, that the ones with largest W become the ones wit smallest W. i.e. idetify edge with largest W (W_max) and smallest W (W_min) and calculate new edge weights as:
   W_new = W_max - W_current + W_min
   (W_min is added just so the originally strongest edge will not become 0, thus deleted) In this case obviously the original concept of F_attr ~ W will be kept. Here the display of the edge (line thickness) would not need to be modded.

In principle either of the two options could be included as a clickable option that can be selected/de-selected in the option menu for ForceAtlas2 where other parameters are set.

There is currently a pull by astraey to rescale edge weights when negative W is in the graph (#1733). So he already knows what to modify in case of scenario 2.

Could be useful for many people, since NetworkX has now the option to dump graphs into .gexf format by one command https://networkx.github.io/documentation/stable/reference/readwrite/gexf.html but it obviously writes the weight that are used in NetworkX.
I would really appreciate if this could be solved ;) Thanks'.

Steps to Reproduce

Context

Your Environment

• Version used: Gephi 0.9.2
• Java version:
• Operating System:

[eduramiba]

Hi,
I think this could be an option in force atlas, if checked, weights would be inverted. If not checked (the default) it will still work as always. Does that sound right?

I guess it would not be too difficult to implement. I will take a look.

[vlado-s]

Yes, that is how I intended (imagined) it to be - check/uncheck to change the usage of W. Thank you eduramiba

[worknet-bienew]

@eduramiba , I'm trying to calculate shortest path using the shortest path feature, my data have weights and higher the weight, stronger the nodes connection. However, the shortest path in Gephi, chooses the one with lowest weight. I understand, this topic is talking about the same issue, what I didn't understand, is the resolution you provided. Can you please explain how I can achieve the shortest path using the highest weight? Thank you for you time!!!

[vlado-s]

@worknet-bienew I think it's not implemented yet - it's added to the wishlist & maybe will be in 0.9.3.
Your case, when large weight represents strong connection is the default interpretation in Gephi, so it should work fine... strange.

[worknet-bienew]

vlado-s thank you for your response. I believe Gephi uses Dijkstra’s algorithm to calculate the shortest path which considers lower weights to find the shortest distance. For this reason, I wish there was something called longest distance algorithm ;) Anyway, at least I know it's not possible in Gephi. Would you know what happens, when I remove the weights or make them all equal to 1, how does it calculate the shortest path? Does it consider highest degree?

[jacomyma]

Comments:

• This issue cannot be addressed at the global level, because it is the job of each algorithm to take in charge weights their own way. Some existing or future plugins might do.
• If you want to change the weights in all of Gephi, then you might as well just actually change them all, for instance by exporting the edges to a spreadsheet, applying a formula, then reimporting the table.
• This issue arises in layouts as well as statistics, so the GitHub issue should ultimately split into multiple ones; but it does not make sense for every layout and every statistic computation.
• I could add a switch to Force Atlas 2 to inverse the weights, but in fact that is already what you would obtain if you used -1 in the "Edge weight influence" setting, which is in practice a exponent added to the weights (2 is square, -1 is inverse). https://github.com/gephi/gephi/blob/master/modules/LayoutPlugin/src/main/java/org/gephi/layout/plugin/forceAtlas2/ForceAtlas2.java#L225
• That being said, it gives me some weird results so there might still be something broken here? To investigate.

[jacomyma]

Issue not exactly addressed, but note that a setting to normalize edge weights between 0 and 1 has been added to Force Atlas 2. 86ca069