Incorrect/unintended behavior when computing significance score in the undirected case #5
Description
When computing alpha values in the undirected case, the result is graph traversal order dependent. Consider two nodes A and B, connected to each other and each of them with more than one neighbor; what the implementation currently does is as follows:
- Move through the original graph (to compute the alpha values for all edges)
- When A (or B) is found, compute the alpha values for all edges around A
- Add the edges to the new graph with the corresponding alphas; notice that edge A-B now has value alpha-A (alpha value considering the neighborhood of A)
- When B is found, compute a new alpha value for edge A-B which instead depends on the neighborhood of B, call it alpha-B
- When trying to add edge B-A (which is the same as A-B since the graph is undirected) to the new graph, the value of alpha-B overwrites alpha-A
- The final alpha value for edge A-B is the one corresponding to the last visited of the two
Networkx does not perform any check, it simply overwrites without warning. The result seems to be consistent given a fixed graph, probably due to the fact that networkx graph traversal order is deterministic; adding a new node C could change the traversal order and thus whether A-B gets value alpha-A or alpha-B.
I assume this is an unintended behavior to be fixed; if intended (assume that the two values are similar therefore either one is fine, though it is a rather forceful assumption), it should still be noted in the readme.