<p>The fastest Betweenness algorithm that I'm aware of is <a href="http://algo.uni-konstanz.de/publications/b-fabc-01.pdf" rel="nofollow noreferrer">the one by Brandes</a>. It runs in O(nm), i.e., if your graph is sparse, that's significantly faster. The algorithm is reasonably complex and probably not implemented in neo4j. However, implementing it should be possible.</p>

<p>Why are you using neo4j? Are your graphs so large that they don't fit in main memory? I don't know neo4j, but that seems their selling point: They can do computations in external memory. If that is not the case, I would strongly recommend to load the whole graph into some simple representation in RAM, and doing your computation there. That's almost always faster than working on some database backend.</p>

<p>However, if your graphs are too large for main memory, you might want to consider alternative algorithms that are especially suited for external computation. You perhaps also want to consider algorithms that don't compute Betweenness exactly, but only approximatively. </p>

<p>Let me quote from the work of <a href="https://arxiv.org/pdf/1510.07971.pdf" rel="nofollow noreferrer">Bergamini and Meyerhenke</a>, which gives a very good literature overview (the references in […] can be found in the paper):</p>

<blockquote>
  <p>The fastest existing
  method for the exact BC computation, BA, requires Θ(nm) operations for
  unweighted graphs and Θ(nm+n 2 log n) for graphs with positive edge
  weights [7]. BA computes [… description of the algorithm left out …] Based on this concept, some algorithms for an approximation of
  BC have been developed. Brandes and Pich [8] propose to approximate
  cB(v) by extrapolating it from the contributions of a subset of source
  nodes, also called pivots. Selecting the pivots uniformly at random,
  the approximation can be proven to be an unbiased estimator for cB(v)
  (i.e. its expectation is equal to cB(v)). In a subsequent work,
  Geisberger et al. [14] notice that this can overestimate BC scores of
  nodes close to the pivots. To limit this bias, they introduce a
  scaling function which gives less importance to contributions from
  pivots that are close to the node. Bader et al. [1] approximate the BC
  of a specific node only, based on an adaptive sampling technique that
  reduces the number of pivots for nodes with high centrality.
  Chehreghani [9] proposes alternative sampling techniques that try to
  minimize the number of samples. Different from the previous approaches
  is the approximation algorithm by Riondato and Kornaropoulos [25],
  which samples a single random shortest path at each iteration. This
  approach allows a theoretical guarantee on the quality of
  approximation. </p>
</blockquote>
A faster betweenness algorithm
<p>Is anyone aware of a faster method to find betweenness of all nodes in a graph database in neo4j?</p>

<p>Currently, I am using an O(n^2) solution where I find the shortest path between each possible pair of nodes.</p>

<p>Any leads or implementations will be much appreciated. Especially if it's in python.</p>