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.

Sign up for GitHub

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

Jump to bottom

Improve performance of Closeness Centrality #174

Open
pankajgupta opened this issue Mar 11, 2015 · 3 comments
Open

Improve performance of Closeness Centrality #174

pankajgupta opened this issue Mar 11, 2015 · 3 comments
Labels
enhancement newbie

Comments

@pankajgupta
Copy link
Contributor

Currently the code performs a new Breadth-first-search for every node. Improve its performance.
@pankajgupta
Copy link
Contributor Author

Benchmark results reported in #173 show actual absolute numbers on speed.

@pankajgupta
Copy link
Contributor Author

One potential algorithm is to first find strongly connected components of the given graph G (http://en.wikipedia.org/wiki/Strongly_connected_component). All the nodes of a single SCC must have the same value of number of nodes reachable. So consider the condensation of G which is a DAG. and obtain the number of reachable nodes from each node in this DAG (perhaps by doing modified breadth-first-search traversals starting from nodes with no incoming edges).

There might be other / better algorithms around.

@bmckown
Copy link
Contributor

bmckown commented Mar 11, 2015

+1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement newbie
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@pankajgupta @bmckown