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
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
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
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));
bc.reduceAdd(v, delta.get(v));
});
});
}
}
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
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
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
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
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.add(g.getRandomVertex());
}
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))));
bc.reduceAdd(v, delta.get(v));
});
});
}
}
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
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();
seeds.add(randomSeed);
}
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
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
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
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();
seeds.forSequential(set::add);
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))));
bc.reduceAdd(v, delta.get(v));
});
});
}
}
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
procedure bc_seeds(graph G, nodeSeq seeds; vertexProp<double> bc) {
G.bc = 0; // Initialize
nodeSet set;
for (s: seeds.items) {
set.add(s);
}
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
}
}
}