基于NetworkX-Python快速近似计算中心性（紧密性、中介性）的方法问询

Absolutely, dealing with a 10k-node directed graph using NetworkX’s exact centrality functions can feel like waiting forever—approximation is the key to getting results in a reasonable timeframe. Let’s walk through practical, tested methods for both closeness and betweenness centrality:

Approximating Closeness Centrality #

The exact nx.closeness_centrality() calculates shortest paths from every node to all others, which is O(n(n+m)) for a graph with n nodes and m edges—way too slow for n=10k. Here’s what to use instead:

• NetworkX’s Built-in Approximation Function
  NetworkX has a dedicated approximation.closeness_centrality() that uses random sampling of source nodes to estimate average shortest path lengths. Instead of computing paths from every node, it picks a subset of k nodes, calculates their paths to all reachable nodes, and extrapolates to estimate closeness for every node.
  Example usage:

  from networkx.algorithms import approximation
  approx_closeness = approximation.closeness_centrality(your_digraph, k=150)
  

  Adjust k based on your accuracy needs: higher k means more precision but longer runtime. For 10k nodes, k=100-200 usually strikes a good balance.

• Handle Non-Strongly Connected Graphs
  In directed graphs, nodes in separate strongly connected components (SCCs) can’t reach each other. Precompute SCCs with nx.strongly_connected_components(G) and calculate closeness within each component—this reduces the effective size of each computation and avoids wasted work on unreachable nodes.

Approximating Betweenness Centrality #

Exact betweenness (nx.betweenness_centrality()) is even more expensive, as it computes all shortest paths between every pair of nodes. The approximation approach here focuses on sampling node pairs instead of checking all of them:

• NetworkX’s Approximation for Betweenness
  Use approximation.betweenness_centrality(), which samples k source nodes, computes shortest paths from each to all others, and counts how often each node lies on these sampled paths. This cuts the runtime drastically compared to the exact method.
  Even better, you can enable parallel processing with the workers parameter to leverage multiple CPU cores:

  approx_betweenness = approximation.betweenness_centrality(your_digraph, k=200, workers=4)
  

  Again, tune k—start with 200 for 10k nodes and adjust if you need more accuracy.

• Skip Normalization if Unnecessary
  If you don’t need normalized centrality scores, set normalized=False in the approximation function. This saves a bit of extra computation time.

Bonus Optimization Tips #

• Consider Faster Libraries
  If you’re open to stepping outside NetworkX, libraries like igraph have far more optimized centrality implementations (both exact and approximate) that handle 10k-node graphs in a fraction of the time. But if you need to stick with NetworkX, the approximation functions are your best bet.
• Filter Redundant Edges
  If your graph has redundant edges (e.g., multiple edges between the same pair of nodes), simplify it with nx.DiGraph(G) (which removes duplicates) before running calculations—fewer edges mean faster shortest path computations.

内容的提问来源于stack exchange，提问作者koushik meneni