1

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...

Improve this question

1 Answer 1

Reset to default
1

Just so that it's clear, k can equal n (your nb_node). From the networkx documentation you link to: "The value of k <= n where n is the number of nodes in the graph. Higher values give better approximation."

If it's not computationally feasible to let k = n then you need to decide on a sample size, and as the documentation says, the larger is generally the better. What matters, however, is the absolute size of the sample, and not the size of the sample relative to the population size (here is a freely available article that discusses this perhaps counter-intuitive point). This means that your are probably better off setting k to a relatively arbitrary, large and computationally tractable number (such as 9999 to throw something out without knowing more about the context), rather than applying your formula which depends on the population size.

More on determining sample size can be found on the Wikipedia page, with further references. And more in-depth questions concerning sample sizes are probably better asked on Cross Validated.

Improve this answer
4
  • 1
    The thing is, and I apologize as I didn't mention it in my question, I need to have a k value based on my population size because my population size is not always the same, and it can range from 2 to 80,000. If my population is 4 and I set k to 9999, wouldn't that be a problem ? Thanks for the article, this really is a counter-intuitive point ! I think I'll go with a fixed value.
    – BFlat
    Commented Nov 22, 2019 at 9:43
  • 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
    Commented Nov 22, 2019 at 10:05
  • 1
    At 80,000 nodes, networkx takes forever (I gave up after 20 minutes) to calculate betweenness, that's why I need to reduce the number of nodes. Furthermore, I need the calculation to be rather 'quick', like 10 seconds top, as it's an analysis platform and a whole bunch of other graph indexes need to be calculated.
    – BFlat
    Commented Nov 22, 2019 at 16:02
  • 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
    Commented Nov 22, 2019 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.