Betweenness Centrality

In Graph Algorithms v3.5, Betweenness Centrality was surfaced in two different procedures:

  • algo.betweenness and algo.betweenness.stream

  • algo.betweenness.sampled and algo.betweenness.sampled.stream

These two have been merged into a single procedure gds.betweenness with all four execution modes supported. The sampling is controlled via configuration parameter rather than explicit procedures. Setting the sampling size to the node count will produce exact results.

Table 1. Changes in Configuration
Graph Algorithms v3.5 Graph Data Science v1.3

stats

-

strategy

-

probability

-

-

samplingSize

-

samplingSeed

maxDepth

-

direction

-

concurrency

concurrency

readConcurrency

readConcurrency [1]

writeConcurrency

writeConcurrency [2]

writeProperty

writeProperty [2]

write

-

graph

-

1. Only when using anonymous graph

2. Only for write mode

Table 2. Changes in YIELD fields
Graph Algorithms v3.5 Graph Data Science v1.3

centrality

score [3]

nodes

-

minCentrality

minimumScore

maxCentrality

maximumScore

sumCentrality

scoreSum

loadMillis

createMillis

evalMillis

computeMillis

writeMillis

writeMillis

-

postProcessingMillis

-

configuration [4]

-

nodePropertiesWritten [5]

write

-

writeProperty [6]

-

3. Only for stream mode

4. The configuration used to run the algorithm

5. Only for write mode

6. Inlined into configuration

Table 3. Betweenness Centrality Stream Mode
Graph Algorithms v3.5 Graph Data Science v1.3

Minimalistic stream over named graph:

CALL algo.betweenness.stream(null, null, {graph: 'myGraph'})
YIELD nodeId, centrality
CALL gds.betweenness.stream('myGraph')
YIELD nodeId, score

Minimalistic stream over named graph, sampled:

CALL algo.betweenness.sampled.stream(null, null, {graph: 'myGraph', probability: 0.5})
YIELD nodeId, centrality
CALL gds.betweenness.stream('myGraph', {samplingSize: 1000}) // assume 2000 nodes
YIELD nodeId, score

Minimalistic streaming over anonymous graph:

CALL algo.betweenness.stream(
  'MyLabel',
  'MY_RELATIONSHIP_TYPE'
)
CALL gds.betweenness.stream({
  nodeProjection: 'MyLabel',
  relationshipProjection: 'MY_RELATIONSHIP_TYPE'
})

Streaming over anonymous graph with UNDRECTED relationship orientation:

CALL algo.betweenness.stream(
  'MyLabel',
  'MY_RELATIONSHIP_TYPE',
  { undirected: true }
)
CALL gds.betweenness.stream({
  nodeProjection: 'MyLabel',
  relationshipProjection: {
    MY_RELATIONSHIP_TYPE: {
      orientation: 'UNDIRECTED'
    }
  }
})
Table 4. Betweenness Centrality Write Mode
Graph Algorithms v3.5 Graph Data Science v1.3

Running write mode on named graph:

CALL algo.betweenness(
  null,
  null,
  {
    graph: 'myGraph',
    writeProperty: 'myWriteProperty',
    write: true
  }
)
YIELD
  nodes,
  minCentrality,
  maxCentrality,
  sumCentrality,
  loadMillis,
  evalMillis,
  writeMillis
CALL gds.betweenness.write(
  'myGraph',
  {
    writeProperty: 'myWriteProperty'
  }
)
YIELD
  nodePropertiesWritten,
  minimumScore,
  maximumScore,
  scoreSum,
  createMillis,
  computeMillis,
  writeMillis,
  configuration