# Determining best k node sample to approximate betweenness centrality

I'm looking for a way to approximate the calculation of betweenness centrality over nodes of a large spatial graph.

I know that igraph in R has a tool to approximate this index: estimate_betweenness()

The networkx python library also provide a tool to approximate the betweenness: betweenness_centrality

Now all those tools are asking for a sample of nodes on which the index calculation will be made. I want to use networkx, and the tool asks for a number of nodes it will randomly pick to constitute the sample.

My question is: how can I determine the best value of k (number of nodes) to sample from my graph, in order to keep the best ratio precision/time-efficiency? My idea involved a formula that could go like:

``````k = nb_node * x
``````

where k is the number of nodes to sample from the graph, nb_node the number of nodes in the graph, and x some kind of magical number that would resolve all my problems...

• Right, and it's out of the question to just always let k = n? I mean at 80,000 nodes it might take a minute, but it's probably worth it if at all possible, and its not that far off from 9999. As for setting k to anything above n I would assume the function then simply uses n, but you should try just to make sure. If you not you could always pass everything through something like `if n < 9999: betweenness_centrality(..., k = n) else: betweenness_centrality(..., k = 9999)` – humperderp Nov 22 '19 at 10:05
• FYI, setting a k higher than the number of nodes throws an error. A simple `if` statement with `number_of_nodes(graph)` solved the issue. Weird thing, I finally reached 10 seconds of calculation with a k value of 40... That can't be right. – BFlat Nov 22 '19 at 16:18