-
-
Notifications
You must be signed in to change notification settings - Fork 3.2k
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
Unstable and Incorrect "nx.eigenvector_centrality_numpy" result when the graph is disconnected #6888
Comments
One of the difficulties with using eigenvectors for measuring centrality is when the adjacency matrix has largest eigenvalue with a multiplicity greater than 1. Said another way, there is a plane (or even 3 or more D space) of eigenvectors with that eigenvalue. Normally the Perron-Frobenius Theorem ensures that there is only a line of eigenvectors for the largest eigenvalue (can't be less than a line because any multiple of an eigenvector is also an eigenvector). We normally select a unique eigenvector by choosing a unit vector with first nonzero element positive. But the P-F theorem doesn't hold when the the network is disconnected (in other language: when the matrix is reducible). Then there is an entire plane (or more) of eigenvectors for the largest eigenvalue and the computed eigenvectors reflect a correct eigenvector, but only one of many. Depending on the method used, round-off error can affect which of the infinitely many choices of eigenvector may be reported. They are all correct as eigenvectors, but can't easily be used for centrality measures. The python version of |
Hello @dschult, Thank you for your quick and valuable response. I agree that the unexpected behavior of However, the results are incorrect concerning the intended purpose of I've surveyed how other graph libraries tackle this challenge in disconnected graphs, and you can find the details here: link. I've identified two primary solutions to address this undefined behavior and enhance NetworkX's robustness:
Considering the fairly robust of Best regards, |
Thank you for these suggestions!! But it does mean that we would need to check whether the graph is disconnected for every call of the function. I haven't looked at how much that slowdown would be. If it is significant, maybe we could put a warning in the doc_string that results may not be effective for disconnected graphs. We could test whether the timing is significant or not by timing a two step process of |
Thanks for considering suggestions and fixing it. Intuitively, I think that checking whether the graph is connected will not significantly reduce the efficiency, since it only needs O(n) time complexity, compared the time cost of computing eigenvectors. I also totally agree with you that we should test their real performance. For me, I will be more happy if you could finally fix the undefined behavior. Thanks once again for your valuable comments. Best regards, |
Hello! Sorry for bothering you again!
I found that when the graph is disconnected, the result of the
nx.eigenvector_centrality_numpy
is unstable and different from thenx.eigenvector_centrality
. Here is the reduced test case with 4 nodes and 2 edges:Step to Reproduce:
Results:
I believe that it may be related to a logic bug in the implementation of
nx.eigenvector_centrality_numpy
. Would it be possible for you to further confirm and investigate it?Best regards,
Joye
Environments
NetworkX: 3.1
Python: 3.10
The text was updated successfully, but these errors were encountered: