search

franktakes / teexgraph

C++ library for large-scale network analysis and computation
GNU General Public License v3.0
24 stars 8 forks source link

Exact algorithm for closeness centrality #1

Closed sgk98 closed 6 years ago

sgk98 commented 6 years ago

The implementation for closeness centrality seems to rely on the paper which uses sampling to only gives an estimate of closeness centrality. While this works well in practice, this is not an exact algorithm(as is claimed in the wiki). Could you point me to the state of the art algorithm/paper(either sequential or parallel) which computes the exact values for closeness centrality? I could possibly try implementing it and adding it to this library.

Thanks

franktakes commented 6 years ago

Thanks for your comment @sgk98 ! Great to see that someone other than me is looking into this code in detail.

Actually, when the function is called with default parameter inputsamplesize = 1.0, the sampling part is not executed in the for-loop that iterates over all nodes, but instead exact computation is done, e.g. the part from line 103 onwards at: https://github.com/franktakes/teexgraph/blob/2dbe9dfd99859a6516304c98a665ca180a8061a3/src/CenGraph.cpp#L103

So, unless I am mistaken in some way, it does implement the exact algorithm as well as the sampling one. Does this answer your question?

franktakes commented 6 years ago

Given no reply in some time, I will close this thread. Let me know should there still be any remaining issues.