Re: [igraph] cut-offs and betweenness/closeness centrality

[Tamas Nepusz]

Hi Jan,

> Unfortunately I can't find any scientific reference how such a cutoff
> influences the validity of the results. Are there any such references
> available? Or any rules of thumb?
Unfortunately I am not aware of any such references -- to be honest, the cutoff
option was introduced only as kind of "quick hack" to allow a rudimentary form
of estimation. NetworkX seems to implement a different estimation method for
betweenness:

http://networkx.lanl.gov/reference/generated/networkx.algorithms.centrality.betweenness_centrality.html

The method that NetworkX uses involves taking a random sample of the nodes in
the network and then calculating shortest paths from these nodes only to all the
other nodes. The size of the sample then determines the precision of the
approximation. The idea is outlined in this paper:

http://www.inf.uni-konstanz.de/algo/publications/bp-celn-06.pdf

Other references that might prove to be relevant:

http://www.cc.gatech.edu/~mihail/WAW07.pdf
http://cs.brown.edu/~matteo/papers/RiondatoKornarop-BetweennessSampling.pdf

Another solution that you might use is to calculate and log the shortest paths
from different source nodes into separate files, using separate igraph
processes, and then accumulate the shortest paths in a post-processing stage to
obtain the actual betweenness scores. This method is useful if you have access
to one or more computers with many CPU cores as each CPU core can then be
responsible for processing a different source node, and the computations can
run in parallel. (igraph is single-threaded by nature, so it will use only
a single CPU core for betweenness calculation, even if you have more than one
core).

All the best,
-- 
T.