Comments:

### General: A very simple and very scalable algorithm with theoretical guarantees to compute an approximation of the closeness centrality for each node in the graph. Maybe the framework can be adapted to solve other problems. In particular, "Hoeffding's theorem" is very handy. ### Parallelism: Note that the algorithm is embarrassingly parallel (the loop over the $k$ reference nodes can be done in parallel with almost no additional work). ### Experiments: It would be nice to have some experiments on large real-world graphs. An efficient (and parallel) implementation of the algorithm is available here: https://github.com/maxdan94/BFS ### Related work: More recent related work by Paolo Boldi and Sebastiano Vigna: - http://mmds-data.org/presentations/2016/s-vigna.pdf - https://arxiv.org/abs/1011.5599 - https://papers-gamma.link/paper/37 It also gives an approximation of the centrality for each node in the graph and it also scales to huge graphs. Which algorithm is "the best"?

You comment anonymously! You will not be able to edit/delete the comment.

Please consider to register or login.

Use $\LaTeX$ to type formulæ and markdown to format text.
When you post something to which you hold the copyright you authorise us to do distribute this data across the scientific community. You can post public domain content. All user-generated content will be freely available online. Please see this page to learn more about Papersγ's terms of use and privacy policy.