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 ComplexityO(N*E)This algorithm might take a long time to run!Space RequirementO(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

/*
*/
//-------------------------------------------------------------
// 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 ComplexityO(k*E) [k = input param]Space RequirementO(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

/*
*/
//-------------------------------------------------------------
// 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 ComplexityO(k*E) [k = no. of given seed nodes]Space RequirementO(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

/*
*/

//-------------------------------------------------------------
// 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
}
}
}