Add more centrality measures #441
Labels
Comments
georgios-ts
added
enhancement
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this issue
Jun 4, 2022
This commit adds a new function eigenvector_centrality() to compute the eigenvector centrality of a graph. It uses the same power function approach that the NetworkX function eigenvector_centrality() [1] function uses. This is for two reasons, the first is that a more traditional eigenvector linear algebra/BLAS function would either require us to link against BLAS at build time (which is a big change in the build system and a large requirement) or to call out to numpy via python both of which seemed less than ideal. The second reason was to make handling holes in node indices bit easier. Using this approach also enabled us to put the implementation in retworkx-core so it can be reused with any petgraph graph. Part of Qiskit#441
mergify bot
pushed a commit
that referenced
this issue
Jun 11, 2022
* Add Eigenvector centrality function This commit adds a new function eigenvector_centrality() to compute the eigenvector centrality of a graph. It uses the same power function approach that the NetworkX function eigenvector_centrality() [1] function uses. This is for two reasons, the first is that a more traditional eigenvector linear algebra/BLAS function would either require us to link against BLAS at build time (which is a big change in the build system and a large requirement) or to call out to numpy via python both of which seemed less than ideal. The second reason was to make handling holes in node indices bit easier. Using this approach also enabled us to put the implementation in retworkx-core so it can be reused with any petgraph graph. Part of #441 * Fix issues with docstrings Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com> * Correct default value of max_iter Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com> * Apply suggestions from code review Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com> * Fix compiler warning * Switch to a Vec<f64> instead of HashMap to track centrality * Update retworkx-core tests too * Fix handling of parallel edges This commit fixes an issue where we were overcounting parallel edges in the graph. There was a bug in the logic that was calculating the combined weight of parallel edges incorrectly. Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com> * Precompute weight edges from python interface This commit changes the callback from the retworkx functions for determining edge weight to precompute them to avoid requiring a python context in the callback. This make a minor improvement in runtime since we only callback to python once at the very beginning instead of in the middle of the loop. * Apply suggestions from code review Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com> * Update src/centrality.rs Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com> * Add docs to toc Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com>
Merged
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
What is the expected enhancement?
Recently a new function that calculates the
betweenness_centralitywas added (https://qiskit.org/documentation/retworkx/api.html#centrality). We can add similar measures likeedge_betweenness_centralityhttps://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.edge_betweenness_centrality.html#networkx.algorithms.centrality.edge_betweenness_centrality, orcloseness_centralityhttps://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.closeness_centrality.html#networkx.algorithms.centrality.closeness_centralityThe text was updated successfully, but these errors were encountered: