Overview

Betweenness centrality quantifies the likelihood that a node lies on the shortest paths between any two other nodes. This metric effectively identifies "bridge" nodes that facilitate connectivity between different parts of a graph.

Betweenness centrality values range from 0 to 1, with higher scores indicating nodes that exert greater influence over the flow and connectivity of the network.

References:

• L.C. Freeman, A Set of Measures of Centrality Based on Betweenness (1977)
• L.C. Freeman, Centrality in Social Networks Conceptual Clarification (1978)

Concepts

Shortest Path

The shortest paths between two nodes are the paths that contain the fewest edges. The Betweenness Centrality algorithm does not take edge weights into account when determining the shortest paths.

Betweenness Centrality

Betweenness centrality of a node x is computed by:

where,

• i and j are two distinct nodes in the graph, excluding x.
• σij is the total number of shortest paths between i and j.
• σij(x) is the number of shortest paths between i and j that pass through node x.
• σij(x)/σij gives the probability that x lies in the shortest paths between i and j. Note that if i and j are not connected, σij(x)/σij is 0.
• k is the total number of nodes in the graph, and the number of ij pairs is calculated as (k-1)(k-2)/2.

The betweenness centrality of node A is computed as: (0 + 1/2 + 1 + 0 + 2/3 + 0) / 6 = 0.3611.

Sampling

This algorithm requires substantial computational resources when applied to large graphs. When the number of nodes in a graph exceeds 10,000, it is recommended to sample by nodes or edges for an approximate computation. The algorithm performs a single uniform sampling.

Considerations

• The betweenness centrality of an isolated node is 0.
• The Betweenness Centrality algorithm ignores the direction of edges. When no sampling is performed, in a graph of k nodes, there are (k-1)(k-2)/2 node pairs considered.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().node_schema("user").edge_schema("know")
insert().into(@user).nodes([{_id:"Sue"}, {_id:"Dave"}, {_id:"Ann"}, {_id:"Mark"}, {_id:"May"}, {_id:"Jay"}, {_id:"Billy"}])
insert().into(@know).edges([{_from:"Dave", _to:"Sue"}, {_from:"Dave", _to:"Ann"}, {_from:"Mark", _to:"Dave"}, {_from:"May", _to:"Mark"}, {_from:"May", _to:"Jay"}, {_from:"Jay", _to:"Ann"}])

Running on HDC Graphs

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_betweenness:

CALL hdc.graph.create("hdc-server-1", "hdc_betweenness", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_betweenness", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: betweenness_centrality

File Writeback

CALL algo.betweenness_centrality.write("hdc_betweenness", {
  params: {
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "betweenness_centrality"
    }
  }
})

algo(betweenness_centrality).params({
  projection: "hdc_betweenness",
  return_id_uuid: "id"
}).write({
  file: {
    filename: "betweenness_centrality"
  }
})

Result:

_id,betweenness_centrality
Mark,0.133333
Jay,0.0666667
Ann,0.133333
Sue,0
Dave,0.333333
Billy,0
May,0.0666667

DB Writeback

Writes the betweenness_centrality values from the results to the specified node property. The property type is float.

CALL algo.betweenness_centrality.write("hdc_betweenness", {
  params: {},
  return_params: {
    db: {
      property: 'bc'
    }
  }
})

algo(betweenness_centrality).params({
  projection: "hdc_betweenness"
}).write({
  db:{ 
    property: 'bc'
  }
})

Full Return

CALL algo.betweenness_centrality("hdc_betweenness", {
  params: {
    max_path_length: 2,
    return_id_uuid: "id",
    order: "desc",
    limit: 3
  },
  return_params: {}
}) YIELD bc
RETURN bc

exec{
  algo(betweenness_centrality).params({
    max_path_length: 2,
    return_id_uuid: "id",
    order: "desc",
    limit: 3
  }) as bc
  return bc
} on hdc_betweenness

Result:

Stream Return

CALL algo.betweenness_centrality("hdc_betweenness", {
  params: {
    return_id_uuid: "id"
  },
  return_params: {
  	stream: {}
  }
}) YIELD r
FILTER r.betweenness_centrality = 0
RETURN count(r)

exec{
  algo(betweenness_centrality).params({
    return_id_uuid: "id"
  }).stream() as r
  where r.betweenness_centrality == 0
  return count(r)
} on hdc_betweenness

Result: 2

Running on Distributed Projections

Creating Distributed Projection

To project the entire graph to its shard servers as dist_betweenness:

create().projection("dist_betweenness", {
  nodes: {"*": ["*"]}, 
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true
})

Parameters

Algorithm name: betweenness_centrality

File Writeback

CALL algo.betweenness_centrality.write("dist_betweenness", {
  params: {},
  return_params: {
    file: {
      filename: "betweenness_centrality"
    }
  }
})

algo(betweenness_centrality).params({
  projection: "dist_betweenness"
}).write({
  file: {
    filename: "betweenness_centrality"
  }
})

Result:

_id,betweenness_centrality
Mark,0.133333
Jay,0.0666667
Ann,0.133333
Sue,0
Dave,0.333333
Billy,0
May,0.0666667

DB Writeback

Writes the betweenness_centrality values from the results to the specified node property. The property type is double.

CALL algo.betweenness_centrality.write("dist_betweenness", {
  params: {},
  return_params: {
    db: {
      property: 'bc'
    }
  }
})

algo(betweenness_centrality).params({
  projection: "dist_betweenness"
}).write({
  db:{ 
    property: 'bc'
  }
})