PGX 20.1.1
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

Category ranking and walking

Algorithm ID pgx_builtin_k3a_node_betweenness_centrality

Time Complexity O(V * E) with V = number of vertices, E = number of edges

Space Requirement O(3 * V) with V = number of vertices

Javadoc

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 nodeProp 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; nodeProp<double> bc) {

  G.bc = 0; // Initialize

  foreach (s: G.nodes) {
    // temporary values per vertex
    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
      // 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

Category ranking and walking

Algorithm ID pgx_builtin_k3b_approx_node_betweenness_centrality

Time Complexity O(V * E) with V = number of vertices, E = number of edges

Space Requirement O(3 * V) with V = number of vertices

Javadoc

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 nodeProp 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; nodeProp<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
    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
      // 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

Category ranking and walking

Algorithm ID pgx_builtin_k3c_approx_node_betweenness_centrality_from_seeds

Time Complexity O(V * E) with V = number of vertices, E = number of edges

Space Requirement O(3 * V) with V = number of vertices

Javadoc

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 nodeProp 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; nodeProp<double> bc) {

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

  for (s: seeds.items) {
    set.add(s);
  }

  for (s: set.items) {

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