PGX 20.2.2
Documentation

# Vertex Betweenness Centrality Algorithms

PGX has 3 variants of vertex betweenness centrality: the classic version, and two approximate versions, one with random seeds and the other with specific vertices that are used as seeds.

## Vertex Betweenness Centrality

##### Categoryranking and walkingAlgorithm IDpgx_builtin_k3a_node_betweenness_centralityTime ComplexityO(V * E) with V = number of vertices, E = number of edgesSpace RequirementO(3 * V) with V = number of verticesJavadocAnalyst#vertexBetweennessCentrality(PgxGraph graph) Analyst#vertexBetweennessCentrality(PgxGraph graph, VertexProperty bc)

The Betweenness Centrality of a vertex V in a graph is the sum of the fraction of shortests paths that pass through V from all the possible shortest paths connecting every possible pair of vertices S, T in the graph, such that V is different from S and T. Because of its definition, the algorithm is meant for connected graphs.

### Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
bc vertexProp vertex property holding the betweenness centrality value for each vertex.

### Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class BetweennessCentrality {
public void bcFull(PgxGraph g, @Out VertexProperty<Double> bc) {
bc.setAll(0d); // Initialize

g.getVertices().forEach(s -> {
// temporary values per vertex
VertexProperty<Double> sigma = VertexProperty.create();
VertexProperty<Double> delta = VertexProperty.create();
sigma.setAll(0d);
sigma.set(s, 1d);

// BFS order iteration from s
inBFS(g, s)
.filter(v -> v != s)
.forward(v -> sigma.set(v, v.getUpNeighbors().sum(sigma)))
.backwardFilter(v -> v != s)
.backward(v -> {
delta.set(v, v.getDownNeighbors().sum(w -> (1 + delta.get(w)) / sigma.get(w)) * sigma.get(v));
});
});
}
}
```
```/*
*/

procedure bc_full(graph G; vertexProp<double> bc) {

G.bc = 0; // Initialize

foreach (s: G.nodes) {
// temporary values per vertex
vertexProp<double> sigma;
vertexProp<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
// Summing over BFS children
v.delta =  sum (w:v.downNbrs) {(1 + w.delta) / w.sigma} * v.sigma;
v.bc += v.delta ; // accumulate bc
}
}
}
```

## Approximate Vertex Betweenness Centrality with Random Seeds

##### Categoryranking and walkingAlgorithm IDpgx_builtin_k3b_approx_node_betweenness_centralityTime ComplexityO(V * E) with V = number of vertices, E = number of edgesSpace RequirementO(3 * V) with V = number of verticesJavadocAnalyst#approximateVertexBetweennessCentrality(PgxGraph graph, int k) Analyst#approximateVertexBetweennessCentrality(PgxGraph graph, int k, VertexProperty bc)

This variant of betweenness centrality approximates the centrality of the vertices by just using k random vertices as starting points for the BFS traversals of the graph, instead of computing the exact value by using all the vertices in the graph.

### Signature

Input Argument Type Comment
G graph
num_seeds int number of random vertices to be used to compute the approximated betweenness centrality coeficients.
Output Argument Type Comment
bc vertexProp vertex property holding the betweenness centrality value for each vertex.

### Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class BetweennessCentralityApproximate {
public void betweennessCentralityApproximate(PgxGraph g, int numSeeds, @Out VertexProperty<Double> bc) {
bc.setAll(0d); // Initialize

long maxSeeds = (g.getNumVertices() > numSeeds) ? numSeeds : g.getNumVertices();

VertexSet seeds = VertexSet.create();
while (seeds.size() < maxSeeds) {
}

seeds.forEach(s -> {
// temporary values per vertex
VertexProperty<Double> sigma = VertexProperty.create();
VertexProperty<Double> delta = VertexProperty.create();
sigma.setAll(0d);
sigma.set(s, 1d);

// BFS order iteration from s
inBFS(g, s)
.filter(v -> v != s)
.forward(v -> sigma.set(v, v.getUpNeighbors().sum(sigma)))
.backwardFilter(v -> v != s)
.backward(v -> {
delta.set(v, v.getDownNeighbors().sum(w -> sigma.get(v) / sigma.get(w) * (1 + delta.get(w))));
});
});
}
}
```
```/*
*/

procedure bc_random(graph G, int num_seeds; vertexProp<double> bc) {

G.bc = 0; // Initialize

long max_seeds = (G.numNodes() > num_seeds) ? num_seeds : G.numNodes();

nodeSet seeds;
while (seeds.size() < max_seeds) {
node randomSeed = G.pickRandom();
}

foreach (s: seeds.items) {

// temporary values per vertex
vertexProp<double> sigma;
vertexProp<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
// Summing over BFS children
v.delta = sum (w: v.downNbrs) {v.sigma / w.sigma * (1 + w.delta)};
v.bc += v.delta ; // accumulate bc
}
}
}
```

## Approximate Vertex Betweenness Centrality From seeds

##### Categoryranking and walkingAlgorithm IDpgx_builtin_k3c_approx_node_betweenness_centrality_from_seedsTime ComplexityO(V * E) with V = number of vertices, E = number of edgesSpace RequirementO(3 * V) with V = number of verticesJavadocAnalyst#approximateVertexBetweennessCentralityFromSeeds(PgxGraph graph, PgxVertex... seeds) Analyst#approximateVertexBetweennessCentralityFromSeeds(PgxGraph graph, VertexProperty bc, PgxVertex... seeds)

This variant of betweenness centrality approximates the centrality of the vertices by just using the vertices from the given sequence as starting points for the BFS traversals of the graph, instead of computing the exact value by using all the vertices in the graph.

### Signature

Input Argument Type Comment
G graph
seeds nodeSeq the (unique) chosen vertices to be used to compute the approximated betweenness centrality coeficients.
Output Argument Type Comment
bc vertexProp vertex property holding the betweenness centrality value for each vertex.

### Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSequence;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class BetweennessCentralityApproximateSeeds {
public void betweennessCentralityApproximate(PgxGraph g, VertexSequence seeds, @Out VertexProperty<Double> bc) {
bc.setAll(0d); // Initialize

VertexSet set = VertexSet.create();

set.forSequential(s -> {
// temporary values per vertex
VertexProperty<Double> sigma = VertexProperty.create();
VertexProperty<Double> delta = VertexProperty.create();
sigma.setAll(0d);
sigma.set(s, 1d);

// BFS order iteration from s
inBFS(g, s) //
.filter(v -> v != s) //
.forward(v -> sigma.set(v, v.getUpNeighbors().sum(sigma))) //
.backwardFilter(v -> v != s) //
.backward(v -> {
delta.set(v, v.getDownNeighbors().sum(w -> sigma.get(v) / sigma.get(w) * (1 + delta.get(w))));
});
});
}
}
```
```/*
*/

procedure bc_seeds(graph G, nodeSeq seeds; vertexProp<double> bc) {

G.bc = 0; // Initialize
nodeSet set;

for (s: seeds.items) {
}

for (s: set.items) {

// temporary values per vertex
vertexProp<double> sigma;
vertexProp<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
// Summing over BFS children
v.delta = sum (w: v.downNbrs) {v.sigma / w.sigma * (1 + w.delta)};
v.bc += v.delta; // accumulate bc
}
}
}
```