PGX 1.2.0
Documentation

Vertex Betweenness Centrality Algorithms

Compute the betweenness centrality value for each node. The value is equal to the number of shortest paths going through the node.


Vertex Betweenness Centrality

Time Complexity O(N*E) This algorithm might take a long time to run!    Space Requirement O(N)

Note that this algorithm is very complex. For large graphs, consider using one of the approximate betweenness centrality approximation algorithms instead (see below).

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
BC nodeProperty node property holding the centrality value for each node.

Green-Marl Code

/*
* Copyright (C) 2015 Oracle and/or its affiliates. All rights reserved.
*/
//-------------------------------------------------------------
// Computation of estimated betweenness centrality
//-------------------------------------------------------------
procedure bc_full(G: graph; BC: N_P<double>) {
  G.BC = 0; // Initialize

  foreach (s:G.nodes) {
    // temporary values per node
    nodeProperty<double> sigma;
    nodeProperty<double> delta;
    G.sigma = 0;
    s.sigma = 1;

    // BFS order iteration from s
    inBFS(v: G.nodes from s) (v != s) {
      // Summing over BFS parents
      v.sigma = sum(w:v.upNbrs) { w.sigma };
    }
    inReverse(v!=s) { // Reverse-BFS order iteration to s
      v.delta =  // Summing over BFS children
        sum (w:v.downNbrs) { (1+ w.delta) / w.sigma } * v.sigma;

      v.BC += v.delta ; // accumulate BC
    }
  }
}

Approximate Betweenness Centrality with random seeds

Time Complexity O(k*E) [k = input param]    Space Requirement O(N)

Computes an approximation of the betweenness centrality value for each node. The implementation performs a breadth first search around k randomly selected nodes to partially compute and approximate the betweenness centrality values.

Signature

Input Argument Type Comment
G graph
k int number of randomly selected seed nodes.
Output Argument Type Comment
BC nodeProperty node property holding the centrality value for each node.

Green-Marl Code

/*
* Copyright (C) 2013 - 2015 Oracle and/or its affiliates. All rights reserved.
*/
//-------------------------------------------------------------
// Computation of estimated betweenness centrality
//-------------------------------------------------------------
procedure bc_random(G: graph, K:int; BC: N_P<double>) {
  G.BC = 0; // Initialize

  int k = 0;
  while (k < K) {
    node s = G.pickRandom();

    // temporary values per node
    nodeProperty<double> sigma;
    nodeProperty<double> delta;
    G.sigma = 0;
    s.sigma = 1;

    // BFS order iteration from s
    inBFS(v: G.nodes from s)(v != s) {
       // Summing over BFS parents
       v.sigma = sum(w:v.upNbrs) { w.sigma };
    }
    inReverse(v != s) { // Reverse-BFS order iteration to s
      v.delta =  // Summing over BFS children
         sum (w:v.downNbrs) {
            v.sigma / w.sigma * (1+ w.delta) };

      v.BC += v.delta ; // accumulate BC
    }

    k++;
  }
}

Approximate Betweenness Centrality with given seeds

Time Complexity O(k*E) [k = no. of given seed nodes]    Space Requirement O(N)

Computes an approximation of the betweenness centrality value for each node. The algorithm is the same as Approximate Betweenness Centrality with random seeds, except that in this version, the user selects the seed nodes.

Signature

Input Argument Type Comment
G graph
seeds nodeSequence seed nodes
Output Argument Type Comment
BC nodeProperty node property holding the centrality value for each node.

Green-Marl Code

/*
* Copyright (C) 2013 - 2015 Oracle and/or its affiliates. All rights reserved.
*/

//-------------------------------------------------------------
// Computation of estimiated betweenness centrality
//-------------------------------------------------------------
procedure comp_BC(G: graph, Seeds: nodeSequence; BC: N_P<double>)  {
  G.BC = 0; // Initialize

  for (s: Seeds.items) { 

    // temporary values per node
    nodeProperty<double> sigma;
    nodeProperty<double> delta;
    G.sigma = 0;
    s.sigma = 1;

    // BFS order iteration from s
    inBFS(v: G.nodes from s)(s != v){
       // Summing over BFS parents
       v.sigma = sum(w:v.upNbrs) { w.sigma };
    }
    inReverse (v!=s) { // Reverse-BFS order iteration to s
      v.delta =  // Summing over BFS children
         sum (w:v.downNbrs) {
            v.sigma / w.sigma * (1+ w.delta) };

      v.BC += v.delta; // accumulate BC
    }
  }
}