The Betweenness Centrality of a vertex is defined as the number of shortest paths that pass through this vertex, divided by the total number of shortest paths. That is
The TigerGraph implementation is based on A Faster Algorithm for Betweenness Centrality by Ulrik Brandes, Journal of Mathematical Sociology 25(2):163-177, (2001). For every vertex s
in the graph, the pair dependency starting from vertex s
to all other vertices t
via all other vertices v
is computed first,
Then betweenness centrality is computed as
According to Brandes, the accumulated pair dependency can be calculated as
For every vertex, the algorithm works in two phases. The first phase calculates the number of shortest paths passing through each vertex. Then starting from the vertex on the most outside layer in a non-incremental order with pair dependency initial value of 0, traverse back to the starting vertex
This algorithm query employs a subquery called bc_subquery. Both queries are needed to run the algorithm.
In the example below, Claire is in the very center of the graph and has the highest betweenness centrality. Six shortest paths pass through Sam (i.e. paths from Victor to all other 6 people except for Sam and Victor), so the score of Sam is 6. David also has a score of 6, since Brian has 6 paths to other people that pass through David.
In the following example, both Charles and David have 9 shortest paths passing through them. Ellen is in a similar position as Charles, but her centrality is weakened due to the path between Frank and Jack.
where is called the pair dependency, is the total number of shortest paths from node s
to node t
and is the number of those paths that pass through v
.
.
.
where, the set of predecessors of vertex w
on shortest paths from s
, is defined as
Characteristic
Value
Result
Computes a Betweenness Centrality value (FLOAT type) for each vertex.
Required Input Parameters
SET<STRING> v_type
: Names of vertex types to use
SET<STRING> e_type
: Names of edge types to use
SET<STRING> re_type:
Names of reverse edge types to use
INT max_hops
: If >=0, look only this far from each vertex
INT top_k
: Sort the scores highest first and output only this many scores
BOOL print_accum
: If True, output JSON to standard output
STRING result_attr
: If not empty, store centrality values (FLOAT) to this attribute
STRING file_path
: If not empty, write output to this file.
BOOL display_edges
: If true, include the graph's edges in the JSON output, so that the full graph can be displayed.
Result Size
V = number of vertices
Time Complexity
O(E*V), E = number of edges, V = number of vertices.
Considering the high time cost of running this algorithm on a big graph, the users can set a maximum number of iterations. Parallel processing reduces the time needed for computation.
Graph Types
Undirected edges, Unweighted edges