Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect/unintended behavior when computing significance score in the undirected case #5

Open
StefanoCretti opened this issue Mar 24, 2023 · 0 comments

Comments

@StefanoCretti
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant